LeetCode 217. 存在重复元素

约 3 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 腾讯 字节 百度
标签
数组 哈希表 排序

题目描述

✅ 217. 存在重复元素

image-20260928230945872

image-20260928230945873

题意分析

判断数组中是否存在两个不同位置，它们保存的数值相同。只要找到任意一组重复就返回 true，所有元素互不相同才返回 false。

重复位置不需要相邻，也没有下标距离限制。题目只问是否存在，不要求返回位置、重复值或出现次数。

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

核心思路

[!blue]

从左到右扫描，用集合 seen 保存当前元素之前已经出现过的所有数值。集合只需要回答是否见过，不必记录完整次数或所有下标。

处理当前值之前先查询集合。如果已经存在，就说明更早某个位置出现过相同值，两个位置不同，已经满足要求，可以立即返回 true。如果不存在，把它加入集合，让后续元素也能与它比较。

每轮结束后，集合恰好包含已扫描前缀中的数值。若整段扫描都没有命中，每个位置的值都不同于它前面的所有值，因此不可能存在任何重复对，最后返回 false。

先查再加入的顺序保证当前元素不会与自身匹配。输入顺序不需要调整，重复值即使相隔很远，也会被集合保留下来的历史信息识别。

解题步骤

  1. 创建空哈希集合。
  2. 依次读取每个值，先判断它是否已在集合中；命中就返回 true。
  3. 未命中时把它加入集合，继续扫描。
  4. 全部处理完仍未发现重复，返回 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(u)$，u 为不同值数量，最坏为数组长度。

关键点总结

[!green]

  • 集合记录的是已经处理的值，让当前位置只与更早位置比较。
  • 存在性问题找到一次重复就能结束，不需要再完成频次统计。
  • 没有距离限制，所以已经出现的值不能因为离得远就被移出集合。

易错点总结

[!yellow]

  • 先加入再查询，会查到当前元素刚刚放入的记录，把非空数组误判为重复。
  • 只比较原数组相邻元素，会漏掉分散在不同位置的相同值。
  • 把“某个值出现两次”理解成必须是两个相邻位置，增加了题目没有的条件。
  • 用列表线性查找历史元素，最坏需要反复扫描前缀，时间会退化为平方级。

相似题目

题目 难度 关联与区别
219. 存在重复元素 II 简单 本题任意两个位置重复即可，原题还限制下标距离，需要维护窗口或最近位置。
220. 存在重复元素 III 困难 重复元素系列。III 同时增加下标差和值差限制，需要维护滑动窗口中的有序候选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/48338292
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！