217. 存在重复元素（简单）

Blind 75 › 217. 存在重复元素（简单） （第 1 章）
文章工具

题目

给定一个整数数组，判断其中是否存在某个数值至少出现两次：有就返回 true，所有元素互不相同则返回 false。

自造示例：[3,1,4,3,5] → true（3 在下标 0 和 3 各出现一次）；[2,0,-2,9] → false（两两都不同）。

约束：数组长度 1 ~ 105；元素为 32 位整数，可取负数，范围约 -109 ~ 109。

思路

一句话：判断“这个数以前有没有出现过”——出现过，就是重复。

最直白的做法：对每个元素，回头和它前面的所有元素逐个比较，一旦相等就返回 true。这需要两层循环，最坏比较 O(n²) 次；当 n = 105 时会达到上百亿次，直接超时。

想更快，先想到排序：排好序后，相同的数必然相邻，扫一遍比较邻居即可，时间 O(n log n)。这已经能通过，但判断“是否重复”其实还有更优解。

关键观察：判重本质是成员查询——“x 是否已经见过”。用一个哈希集合记录见过的元素，查询和插入的平均代价都是 O(1)，于是整个判断降到 O(n)。

为什么必须用哈希集合而不是普通列表？列表的 in 查询要逐个扫描，是 O(n)，总时间又变回 O(n²)；哈希集合才是 O(1) 平均查询。另外，元素有负数且范围达到 109，没法用一个很小的布尔桶数组，集合天然适配任意整数。

解法

维护一个哈希集合 seen，从左到右遍历：

  1. 若 nums[i] 已在 seen 中，立即返回 true。
  2. 否则把它加入 seen，继续下一个。
  3. 遍历结束仍没返回，说明没有重复，返回 false。
当前元素已见集合动作
3{}不在，加入 → {3}
1{3}不在，加入 → {3,1}
4{3,1}不在，加入 → {3,1,4}
3{3,1,4}已在 → 返回 true

整个过程只需一遍遍历，且发现重复后立刻停止，不会做多余工作。

下图把上面 3 个步骤串成流程，并逐步演示：

217. 存在重复元素（简单） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
217. 存在重复元素（简单） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 bool containsDuplicate(vector<int>& nums) {
 unordered_set<int> seen;
 for (int x : nums) {
 if (seen.f
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。