349. 两个数组的交集
题目描述
输入两个整数数组 nums1 和 nums2。
找出同时在两个数组中出现过的所有数值，组成数组返回。每个数值在结果里只放一次，即使它在原数组里重复出现。
结果的顺序不限。
示例 1
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
解释：两个数组都含有 2，结果中只保留一个。
示例 2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
解释：共同出现的数是 4 和 9，写成 [9,4] 也正确。
数据范围
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解题思路：排序 + 二分查找
把 nums2 排序后就可以在它上二分查找。nums1 也排序，这样相同的数挨在一起，重复的直接跳过，结果自然去重。对 nums1 中每个不同的 x，用 bisect_left 在 nums2 中找第一个 >= x 的位置 j，若 nums2[j] == x 就说明 x 在 nums2 里。
为什么正确
res 中是 nums1 已处理部分里、也在 nums2 中出现的不同数字，且按升序排列。
复杂度分析
时间 O(m log m + n log n)，空间 O(1)（不计返回值和排序栈）。
易错点
bisect_left 返回的 j 可能等于 len(nums2)（x 比所有数都大），先判断 j < len(nums2) 再访问 nums2[j]。nums1 中的重复数要跳过，否则结果会重复。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
res = []
for i, x in enumerate(nums1):
if i > 0 and x == nums1[i - 1]:
continue
j = bisect_left(nums2, x)
if j < len(nums2) and nums2[j] == x:
res.append(x)
return resclass Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums1.length; i++) {
int x = nums1[i];
if (i > 0 && x == nums1[i - 1]) {
continue;
}
int j = Arrays.binarySearch(nums2, x);
if (j >= 0) {
res.add(x);
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> res;
for (int i = 0; i < (int)nums1.size(); i++) {
int x = nums1[i];
if (i > 0 && x == nums1[i - 1]) {
continue;
}
int j = lower_bound(nums2.begin(), nums2.end(), x) - nums2.begin();
if (j < (int)nums2.size() && nums2[j] == x) {
res.push_back(x);
}
}
return res;
}
};func intersection(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
res := []int{}
for i, x := range nums1 {
if i > 0 && x == nums1[i-1] {
continue
}
j := sort.SearchInts(nums2, x)
if j < len(nums2) && nums2[j] == x {
res = append(res, x)
}
}
return res
}var intersection = function(nums1, nums2) {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
const res = [];
for (let i = 0; i < nums1.length; i++) {
const x = nums1[i];
if (i > 0 && x === nums1[i - 1]) {
continue;
}
let lo = 0, hi = nums2.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums2[mid] < x) lo = mid + 1;
else hi = mid;
}
if (lo < nums2.length && nums2[lo] === x) {
res.push(x);
}
}
return res;
};function intersection(nums1: number[], nums2: number[]): number[] {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
const res: number[] = [];
for (let i = 0; i < nums1.length; i++) {
const x = nums1[i];
if (i > 0 && x === nums1[i - 1]) {
continue;
}
let lo = 0, hi = nums2.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums2[mid] < x) lo = mid + 1;
else hi = mid;
}
if (lo < nums2.length && nums2[lo] === x) {
res.push(x);
}
}
return res;
}其他解法
哈希集合用 O(m + n) 空间换来线性时间；排序做法只用排序栈空间，结果自然有序，适合输入已经有序的场景。
解法 2：两个哈希集合 时间 O(m + n)，空间 O(m + n)
把 nums1 的元素放进哈希集合。遍历 nums2，如果元素在集合中就加入答案，并把它从集合中删掉，这样重复的值只会被记录一次。
线性时间，不需要排序，也不改动输入数组。需要额外的哈希表空间，输出顺序不保证有序。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
seen = set(nums1)
res = []
for x in nums2:
if x in seen:
res.append(x)
seen.remove(x)
return resclass Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> seen = new HashSet<>();
for (int x : nums1) seen.add(x);
List<Integer> res = new ArrayList<>();
for (int x : nums2) {
if (seen.remove(x)) res.add(x);
}
int[] ans = new int[res.size()];
for (int i = 0; i < ans.length; i++) ans[i] = res.get(i);
return ans;
}
}class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> seen(nums1.begin(), nums1.end());
vector<int> res;
for (int x : nums2) {
if (seen.erase(x)) res.push_back(x);
}
return res;
}
};func intersection(nums1 []int, nums2 []int) []int {
seen := map[int]bool{}
for _, x := range nums1 {
seen[x] = true
}
res := []int{}
for _, x := range nums2 {
if seen[x] {
res = append(res, x)
delete(seen, x)
}
}
return res
}var intersection = function(nums1, nums2) {
const seen = new Set(nums1);
const res = [];
for (const x of nums2) {
if (seen.has(x)) {
res.push(x);
seen.delete(x);
}
}
return res;
};function intersection(nums1: number[], nums2: number[]): number[] {
const seen = new Set<number>(nums1);
const res: number[] = [];
for (const x of nums2) {
if (seen.has(x)) {
res.push(x);
seen.delete(x);
}
}
return res;
}