LeetCode 217. 存在重复元素

2022-11-03 HGNULB 约 8 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 217. 存在重复元素

题意分析

给定一个整数数组，只需回答一个是非问题：是否存在两个不同下标但值相同的元素。注意问的是「存在性」而不是「有几个」「是哪个」「在哪里」，返回值是布尔量，所以一旦拿到证据就可以立刻交卷，不必看完全部数据。

「下标不同、值相同」这个措辞要读准：它约束的是位置必须不同，对值本身没有任何限制。负数、零、重复出现三次以上的数都算数，只要同一个值出现过两次就成立。

题目对数值范围没有做「元素都在 $[1, n]$ 之间」这类限制，数组长度可以到 $10^5$，元素可以是任意 int。这两条约束合起来透露了很强的信号：值域是稀疏且无界的，不能开一个下标即数值的标记数组；$10^5$ 的规模允许 $O(n \log n)$，但显然存在更好的做法，而两两枚举的 $O(n^2)$ 在这个规模下会超时。

还有一条隐含信息：题目没有要求原地、也没有要求不使用额外空间。这等于默许我们拿空间换时间。如果面试官后续追加「不许用额外空间」的限制，做法就得完全换一套。

边界只有两处：空数组和单元素数组。这两种情况下不可能凑出两个不同下标，答案恒为 false。好的实现应该让它们自然落入主循环（循环体一次都不执行，直接走到收尾的 false），而不需要写特判分支。

解法：哈希集合记录已出现数字

核心思路

最朴素的想法是双重循环，对每一对下标 (i, j) 检查 nums[i] == nums[j]。它一定正确，瓶颈在于同一个数字被反复比较了很多次——第 j 个元素要和它前面所有元素逐个比一遍，总共 $O(n^2)$ 次比较，$10^5$ 规模下大约 $5 \times 10^9$ 次操作，必然超时。

观察这个朴素做法在做什么：内层循环的全部工作，其实只是在回答一个问题——「nums[j] 这个值，在前面出现过吗」。而回答这个问题根本不需要逐个扫描，只要维护一份「前面出现过哪些值」的名册，查一次即可。名册的操作只有两种：插入一个值、查询一个值在不在，这正是哈希集合的原生能力，两者都是均摊 $O(1)$。

于是每个元素的处理代价从 $O(n)$ 降到 $O(1)$，整体降到 $O(n)$。这就是「用一次 $O(1)$ 查表替代一轮 $O(n)$ 扫描」这个模式的最简单形态。

循环不变量是：每次准备处理下标 i 之前，集合 seen 恰好等于 {nums[0], ..., nums[i-1]} 这些值的集合，且这段前缀内部没有重复。前半句由「每轮结束都把当前值加入集合」维持；后半句由「一旦发现重复就立即返回」维持——只要循环还在继续，就说明前缀始终是干净的。

有了这个不变量，正确性是两句话：若某轮查到 nums[i] 已在集合中，由不变量的前半句可知它等于某个 nums[k]（k < i），下标必然不同，返回 true 正确；若循环跑完从未命中，由不变量的后半句可知整个数组无重复，返回 false 正确。

另一个思路是先排序再看相邻元素是否相等，正确性同样成立，但要付出 $O(n \log n)$ 的排序代价，而且会破坏原数组顺序。只有在「不许用额外空间」时它才是更优选择。

解题步骤

创建空哈希集合 seen。它代表「已经遍历过的值」，初始为空对应「已遍历前缀为空」，与循环不变量的初始状态一致。Java 用 HashSet<Integer>，Go 用 map[int]bool（Go 没有内置 set，用 map 的键当集合，值只是占位）。

顺序遍历数组的每个数字 num。顺序无所谓正确性，但顺序遍历才能让「已遍历前缀」这个概念成立，也才能在最早的位置提前返回。

先查后插：如果 seen 已包含 num，立即返回 true。这个顺序不能反。若先插入再查询，任何一个数字插进去之后都必然能被自己查到，函数会对所有非空数组返回 true。

否则把 num 加入 seen，维持不变量，让后面的元素能查到它。

遍历结束返回 false。走到这一行说明每个元素都没在它自己的前缀里出现过，等价于全数组无重复。

以 nums = [1, 2, 3, 1] 走一遍。

初始 seen = {}。第一轮 num = 1，seen 不含 1，插入后 seen = {1}。第二轮 num = 2，不含，插入后 seen = {1, 2}。第三轮 num = 3，不含，插入后 seen = {1, 2, 3}。第四轮 num = 1，此时 seen 已含 1，立即返回 true，函数结束。

再以无重复的 nums = [1, 2, 3, 4] 走一遍：四轮查询全部落空，集合依次膨胀到 {1, 2, 3, 4}，循环自然退出，返回 false。

最后以 nums = [] 走一遍：for 的第一次条件判断就失败，循环体零次执行，直接返回 false。这印证了空数组不需要特判——主逻辑天然覆盖。

代码实现

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> seen = new HashSet<>();

        for (int num : nums) {
            // 先查再放，能在第一次发现重复时立即返回。
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }

        return false;
    }
}

func containsDuplicate(nums []int) bool {
    seen := make(map[int]bool)

    for _, num := range nums {
        // 先查再放，能在第一次发现重复时立即返回。
        if seen[num] {
            return true
        }
        seen[num] = true
    }

    return false
}

复杂度分析

时间复杂度：$O(n)$。数组只被扫描一遍，每个元素上做一次查询加最多一次插入，哈希操作均摊 $O(1)$，所以总量与 $n$ 成正比。最坏情况下哈希发生大量冲突会退化到 $O(n)$ 单次操作，但对随机整数不会发生；有重复时往往提前返回，实际远小于一遍。

空间复杂度：$O(n)$。集合里最多装下全部 $n$ 个互不相同的值，这正是无重复数组这一最坏输入。这份空间就是换掉 $O(n^2)$ 时间的代价，题目允许才可以这么做。

关键点总结

遇到「之前是否出现过」「有没有见过」这类判定，第一反应就是哈希集合——它把朴素做法里的一轮 $O(n)$ 扫描压缩成一次 $O(1)$ 查表，这是从 $O(n^2)$ 降到 $O(n)$ 的通用套路。

「先查后插」的顺序本身携带语义：集合里装的必须是严格在当前元素之前出现过的值，顺序一旦颠倒，语义就变成「包括自己」，结论随之失效。

存在性问题可以提前返回，把最坏复杂度和平均复杂度拉开；计数类问题则必须扫完全程，两者的循环结构不能照抄。

用哈希换时间的前提是题目没有空间限制。面试中主动说一句「这里用了 $O(n)$ 额外空间，如果不允许，我改成排序后比较相邻元素，时间变成 $O(n \log n)$ 但空间 $O(1)$」，等于把两种解法的取舍一次讲完。

面试视角：这题本身几乎不设障碍，考官真正想听的是后续追问的应对——「如果数组元素保证在 $[1, n]$ 范围内能否做到 $O(1)$ 空间」（原地标记或环形找入口，即 287 题）、「如果要求重复元素下标之差不超过 k」（滑动窗口维护定长集合，即 219 题）。能顺着追问往下走，才是这道简单题的价值。

易错点总结

先插入再查询：写成 seen.add(num); if (seen.contains(num)) return true;，输入 [1, 2, 3] 会在第一轮就返回 true，因为 1 刚被自己插进去。任何非空数组都返回 true。

用 List 代替 Set 存已见元素：list.contains(num) 是 $O(n)$ 线性扫描，$n = 10^5$ 的无重复数组会做约 $5 \times 10^9$ 次比较，直接超时——代码逻辑完全正确，但等于没优化。

Java 里用 int[] 当计数桶：写成 int[] cnt = new int[100001]，遇到 nums = [-1, -1] 会抛 ArrayIndexOutOfBoundsException，因为题目允许负数；即便全为正，nums = [2000000000, 2000000000] 也会因为开不出这么大的数组而崩溃。

Java 用 == 比较装箱后的 Integer：手写成 if (list.get(j) == num)，输入 [200, 200] 会返回 false——200 超出了 Integer 缓存的 [-128, 127] 区间，两个包装对象引用不同。用 HashSet 的 contains 就绕开了这个坑。

Go 里用 if seen[num] == true 之外的写法误判零值：若把集合写成 map[int]int 并用 if seen[num] != 0 判断，遇到显式存入 0 计数的写法会漏判；用 map[int]bool 配 seen[num]（不存在时取到零值 false）才安全。

排序解法忘了下标从 1 开始比：写成 for i := 0; i < len(nums); i++ { if nums[i] == nums[i+1] }，输入 [1, 2] 在 i = 1 时访问 nums[2] 越界；正确写法是 i 从 1 起、比较 nums[i] == nums[i-1]。

排序解法在原数组上直接排：Arrays.sort(nums) 会改动调用方传入的数组，若题目后续还要用原始顺序（或在多测试用例复用同一数组的场景下），会污染数据；需要先拷贝一份。

误解成「相邻两个元素相同」：只检查 nums[i] == nums[i+1] 而不排序，输入 [1, 2, 3, 1] 会返回 false，漏掉了不相邻的重复对。

对空数组写死特判返回 true：nums = [] 时不存在任何一对下标，正确答案是 false，写反会直接错在第一个用例上。

相似题目

题目	难度	考察点
219. 存在重复元素 II	简单	追加「下标之差不超过 k」的限制，集合要随窗口滑动删除过期元素
220. 存在重复元素 III	困难	值也放宽为「差不超过 t」，哈希失效，需有序集合二分或桶排思想
287. 寻找重复数	中等	值域限定在 $[1, n]$ 且要求 $O(1)$ 空间，转成链表找环入口
442. 数组中重复的数据	中等	要输出全部重复值而非判定，利用值域原地取负做标记
136. 只出现一次的数字	简单	反过来找唯一不重复的那个，异或可以做到 $O(1)$ 空间
349. 两个数组的交集	简单	判重对象从单数组内部变成跨两个数组，需要先把一侧灌入集合再查另一侧
1. 两数之和	简单	同样是边遍历边查表，但查的是 `target - num` 且需返回下标，故用 map 存位置