LeetCode 217简单哈希
存在重复元素 图解题解
数组里有没有重复数字？一个 Set，一次扫描，不用排序，答案就出来了。
就像在一堆快递单号里查是否有重复——与其拿起每张单去和其余每张逐一比对，不如备一个「已见单号本」：扫到一张就先翻本查，没查到再记进去，一旦查到直接喊「重了！」。Set 就是这本随查随记的单号本，每次查和记都是 O(1)，整个扫一遍就搞定，不需要任何回头重扫。
这道题到底在问什么
判断数组中是否存在任意一个重复元素。
- nums
- [1,2,3,1]
- 输出
- true
最优解：一步一步想明白
- 3最直接是每个数和后面所有数比较。数组一长，比较次数会爆炸。
- 4用 set 记录已经见过的数。每来一个数先查，再加入。命中立刻返回 true。
- 5seen={}seen 为空，准备从左到右扫描。
- 6add 11 不在 seen 中，加入。
- 7add 22 也没见过，加入。
- 8add 33 没见过，继续加入。
- 91 在 seen 里扫到第二个 1，先查 seen，发现 1 那一行已经在里面。
- 10return true下标 0 和下标 3 是同一个值，命中重复，立刻返回 true。
- 11all unique如果扫完整个数组都没命中，最后才返回 false。
- 14查到重复就立刻停，不需要继续扫描。
- 17wrong order如果先把当前 1 放进去，再查 seen，当前 1 会命中自己。必须先查。
- 24这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：先 add 再查
✓ 对：先查再 add
先加入会把当前数自己当成重复。
✗ 错：只看相邻元素
✓ 对：用 set 看全局历史
重复元素不一定相邻。
✗ 错：以为需要排序
✓ 对：set 可线性完成
排序会变 O(nlogn)，且没必要。
完整代码（Python / C++ / Java）
Python
class Solution:
def containsDuplicate(self, nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return FalseC++
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) return true;
seen.insert(x);
}
return false;
}
};Java
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (seen.contains(x)) return true;
seen.add(x);
}
return false;
}
}套路模板 · “边扫边记，见过就停” 骨架
# 模型：一边遍历，一边用 set 记“我见过谁”
seen = set()
for x in nums:
if x in seen: # 先查历史
return True # 命中即停
seen.add(x) # 没见过再记下
return False # 扫完都没命中// 模型：一边遍历，一边用 set 记“我见过谁”
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) return true; // 先查历史，命中即停
seen.insert(x); // 没见过再记下
}
return false; // 扫完都没命中// 模型：一边遍历，一边用 set 记“我见过谁”
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (seen.contains(x)) return true; // 先查历史，命中即停
seen.add(x); // 没见过再记下
}
return false; // 扫完都没命中复杂度
时间复杂度
O(n)
每个元素最多查一次、加一次
空间复杂度
O(n)
最坏全部不重复，需要存 n 个数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 存在重复元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不用额外空间吗？+
可以排序后看相邻，但时间变 O(nlogn)，且会改变数组顺序。
这道题为什么用「哈希」，换最直接的暴力解会差在哪？+
哈希抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。