---

1213. 三个有序数组的交集

• 标签：数组、哈希表、二分查找、计数
• 难度：简单

题目链接

• 1213. 三个有序数组的交集 - 力扣

题目大意

描述：给出三个均为严格递增排列的整数数组 $arr1$、$arr2$ 和 $arr3$。

要求：返回一个由仅在这三个数组中同时出现的整数所构成的有序数组。

说明：

• $1 \le arr1.length, arr2.length, arr3.length \le 10^{3}$。
• $1 \le arr1[i], arr2[i], arr3[i] \le 2000$。

示例：

• 示例 1：

输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现。

解题思路

思路 1：三指针

1. 核心思想

因为三个数组都是有序的（严格递增），我们可以用三个指针分别遍历三个数组，每次比较三个指针指向的值。

这就像有三个有序的队伍，每次看三个队伍最前面的人：如果三个人的编号相同，就记录下来并同时向后走一步；否则，找出最小的编号，让对应的队伍向前走一步（因为有序，最小编号不可能在后面出现）。

2. 具体步骤

第 1 步：初始化三个指针 $i$、$j$、$k$ 分别指向三个数组的起始位置（下标 $0$）。

第 2 步：当三个指针都没有超出各自数组范围时，循环比较：

• 如果 $arr1[i] == arr2[j] == arr3[k]$，说明找到了一个公共元素，记录下来，三个指针同时后移。
• 否则，找出三个当前值中的最小值，将对应指针后移：
  • 如果 $arr1[i]$ 最小，$i += 1$。
  • 如果 $arr2[j]$ 最小，$j += 1$。
  • 如果 $arr3[k]$ 最小，$k += 1$。

第 3 步：循环结束后返回结果列表。

结合示例走一遍：

$arr1=[1,2,3,4,5], arr2=[1,2,5,7,9], arr3=[1,3,4,5,8]$

初始化：$i=0, j=0, k=0$

• $arr1[0]=1, arr2[0]=1, arr3[0]=1$ → 相等，记录 $1$，$i=1,j=1,k=1$
• $arr1[1]=2, arr2[1]=2, arr3[1]=3$ → 最小值 $2$，$i=2,j=2$
• $arr1[2]=3, arr2[2]=5, arr3[1]=3$ → 最小值 $3$，$i=3,k=2$
• $arr1[3]=4, arr2[2]=5, arr3[2]=4$ → 最小值 $4$，$i=4,k=3$
• $arr1[4]=5, arr2[2]=5, arr3[3]=5$ → 相等，记录 $5$，$i=5,j=3,k=4$

$i$ 超出范围，结束。结果 $[1,5]$。

思路 1：代码

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        i = j = k = 0
        ans = []
        while i < len(arr1) and j < len(arr2) and k < len(arr3):
            if arr1[i] == arr2[j] == arr3[k]:
                # 三个值相等，记录结果
                ans.append(arr1[i])
                i += 1
                j += 1
                k += 1
            else:
                # 找到最小值，将对应的指针向后移动
                min_val = min(arr1[i], arr2[j], arr3[k])
                if arr1[i] == min_val:
                    i += 1
                if arr2[j] == min_val:
                    j += 1
                if arr3[k] == min_val:
                    k += 1
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n_1 + n_2 + n_3)$，其中 $n_1$、$n_2$、$n_3$ 分别是三个数组的长度。每个指针在最坏情况下会遍历完整个数组。
• 空间复杂度：$O(1)$，不考虑存储结果所需的空间。