LeetCode 2215简单哈希表
找出两数组的不同 图解题解
这道题到底在问什么
给两个整数数组 nums1、nums2。返回 [d1, d2]:d1 是只在 nums1 出现的不同整数，d2 是只在 nums2 出现的不同整数。结果内部各自不含重复，顺序不限。
- 输入
- nums1=[1,2,3], nums2=[2,4,6]
- 输出
- [[1,3],[4,6]]（2 两边都有，不计）
最优解：一步一步想明白
- 3记住「两边各去重成集合 → 各取对方没有的 → 共有的都不要」，下面每帧都在套它。
- 4先处理 nums1。把每个数往集合 s1 里塞，集合天生不存重复，所以塞完就是 nums1 的「不同元素」。盯住右边 s1 怎么长起来。
- 5第 0 位是 1，s1 里还没有，加进去。s1 现在是 {1}。
- 6第 1 位是 2，s1 里还没有，加进去。s1 现在是 {1, 2}。
- 7第 2 位是 3，s1 里还没有，加进去。s1 现在是 {1, 2, 3}。
- 8第 3 位又是 1，s1 里早有了，去重不再加。这就是用集合的好处:重复的自动被挡在外面。
- 9再用同样的办法处理 nums2，逐个塞进集合 s2。两个集合都备好后，剩下的就是互相对照「谁有谁没有」。
- 10第 0 位是 2，加入 s2。s2 现在是 {2}。
- 11第 1 位是 4，加入 s2。s2 现在是 {2, 4}。
- 12第 2 位是 6，加入 s2。s2 现在是 {2, 4, 6}。
- 13第 3 位又是 6，s2 里已经有了，去重跳过。
- 14现在屏幕这排是 s1 的元素 {1, 2, 3}。逐个去问 s2:你有没有这个数?s2 没有的，就是「只在 nums1」的，收进左边答案。
- 151 在 s2 里找不到，说明它只在 nums1，收进左边答案。只在 nums1 = [1]。
- 162 在 s2 里也有，是两边共有的，按规则两边都不要，跳过。
- 173 在 s2 里找不到，说明它只在 nums1，收进左边答案。只在 nums1 = [1, 3]。
- 18换个方向，这排是 s2 的元素 {2, 4, 6}。逐个去问 s1:有没有?s1 没有的，就是「只在 nums2」，收进右边答案。
- 192 在 s1 里也有，又是共有元素，跳过。
- 204 在 s1 里没有，只在 nums2，收进右边答案。只在 nums2 = [4]。
- 216 在 s1 里没有，只在 nums2，收进右边答案。只在 nums2 = [4, 6]。
- 22两个方向都对照完，答案就是 [[1, 3], [4, 6]]。回头看:先各自去重成集合，再各取对方没有的，共有的 2 全程被两次跳过，一遍就分清了。
⚠️ 容易写错的地方
✗ 错：直接对原数组比对、不去重
✓ 对：先各自去重成集合
题目要的是「不同整数」，nums1 里重复的同一个数只能在结果里出现一次
✗ 错：把共有元素也放进某一边
✓ 对：两边都出现的元素两边都跳过
结果要的是「各自独有」，共有元素既不属于 d1 也不属于 d2
✗ 错：只算 s1 − s2 一个方向
✓ 对：两个方向都要算
答案是两个列表，s1−s2 和 s2−s1 都不能漏
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
s1, s2 = set(nums1), set(nums2)
return [list(s1 - s2), list(s2 - s1)]C++
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());
vector<vector<int>> ans(2);
for (int x : s1) if (!s2.count(x)) ans[0].push_back(x);
for (int x : s2) if (!s1.count(x)) ans[1].push_back(x);
return ans;
}
};Java
import java.util.*;
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>();
for (int x : nums1) s1.add(x);
for (int x : nums2) s2.add(x);
List<Integer> a = new ArrayList<>(), b = new ArrayList<>();
for (int x : s1) if (!s2.contains(x)) a.add(x);
for (int x : s2) if (!s1.contains(x)) b.add(x);
List<List<Integer>> ans = new ArrayList<>();
ans.add(a);
ans.add(b);
return ans;
}
}复杂度
时间
O(n + m)
建两个集合各扫一遍，再各遍历集合一次，集合查找 O(1)
空间
O(n + m)
两个哈希集合最多各存下全部不同元素
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找出两数组的不同 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用哈希集合而不是排序后双指针?+
哈希集合建表和查找都是平均 O(1)，总体 O(n+m);排序双指针要 O(n log n + m log m)。数据无序、只问存在性时，哈希集合更直接更快。当然排序双指针也能做，是另一种可接受解。
能不能只用一个集合?+
可以省一点:先把 nums2 建成集合 s2，遍历 nums1 去重并对照 s2 得 d1;但求 d2 时还需要知道 nums1 的去重集合，所以通常两个集合最清晰。用一个集合也能做，代价是多一些临时判断。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 找出两数组的不同 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。