0217. Contains Duplicate

题目信息

题号:
  1. 存在重复元素

难度:

Easy

主题:

数组、哈希集合、排序、存在性判断

原题:

LeetCode 0217

重点:

不同下标、已见值状态、先查询再记录、哈希与排序的取舍

题目重述

给定整数数组 nums,判断是否存在两个不同下标 i、j,使 nums[i] == nums[j]。只返回布尔值, 不需要指出是哪一个值或哪两个下标;数组中的负数、零和正数都按普通整数参与比较。题目不要求改变输入数组, 数组长度最多为 10^5,因此不能把所有位置对都当作同等便宜的操作。

自建示例

nums = [4,1,7,4] 返回 true:最后一个 4 与下标 0 的 4 形成一对不同下标。 nums = [4,1,7] 返回 false;nums = [5] 也返回 false,因为没有两个位置可供比较。

nums = [-2,9,-2] 返回 true,数值大小和正负不影响重复定义。重复值不必相邻,所以只比较相邻输入位置会漏掉答案。

C++ 实现

#include <algorithm>
#include <unordered_set>
#include <vector>

class Solution {
private:
    static bool containsBySorting(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        for (int index = 1; index < static_cast<int>(nums.size()); ++index) {
            if (nums[index] == nums[index - 1]) return true;
        }
        return false;
    }

    static bool containsByHash(const std::vector<int>& nums) {
        std::unordered_set<int> seen;
        seen.reserve(nums.size());
        for (int value : nums) {
            if (!seen.insert(value).second) return true;
        }
        return false;
    }

public:
    bool containsDuplicate(std::vector<int>& nums) {
        return containsByHash(nums);
    }
};

题解

从位置对枚举到值的存在性

最直观的算法枚举每个 i < j,直接比较 nums[i] 和 nums[j]。它覆盖了全部可能的下标对,所以一定正确, 但长度为 n 时最坏需要比较 n(n-1)/2 对,时间复杂度为 O(n^2);即使很早发现重复,无法改善没有重复时的上界。

排序后,相等值必然相邻,只需检查相邻元素,时间降为 O(n log n)。代价是排序获得了题目没有要求的全序,还可能改变输入; 若必须保留输入顺序,就要先复制数组。

题目真正询问的是“当前值是否曾经出现”,不需要知道旧值的顺序、次数或下标。维护一个哈希集合,把与当前值的所有旧位置 压缩成一个“已出现”状态:一次集合查询就替代了当前值与所有旧位置的重复比较。

方法对比

方法

时间

额外空间

被保留或删除的工作

枚举所有位置对

O(n^2)

O(1)

保证不漏解,但反复比较同一个值与许多旧位置

排序后检查相邻值

O(n log n)

原地或 O(n) 副本

用全序消除远距离比较,可能改变输入

扫描加哈希集合

期望 O(n)

O(n)

只保存值是否出现,删除顺序和出现次数

状态定义与转移

处理下标 i 之前,seen 恰好包含前缀 nums[0..i-1] 中出现过的所有不同值,并且此前没有发现重复。 读取 nums[i] 时必须先查询这个前缀状态:

  • 若值已经在 seen 中,说明它在某个更早的下标出现过,两个下标不同,答案立即为 true;

  • 若值不在集合中,把它加入,状态就变成下一个前缀的不同值集合。

先查询再记录是“不同下标”条件在代码中的落点。若先把当前值写入集合再查询,集合已经包含当前元素本身, 就无法区分一次出现和两次出现。由于本题没有下标距离限制,值一旦进入 seen 就永不过期。 因此若扫描在某个位置返回 false,此前每个值都只出现过一次;若数组中确有一对相等值,较大的那个下标被处理时, 较小下标对应的值必已在 seen 中,算法一定会在那里返回 true。

状态走读

对 nums = [4,1,7,4],每次插入的返回值同时告诉我们“是否已见”和“是否需要更新状态”:

当前值

查询前 seen

insert 结果

状态与结论

4

{}

成功

{4},继续

1

{4}

成功

{4,1},继续

7

{4,1}

成功

{4,1,7},继续

4

{4,1,7}

失败

已找到两个不同下标,返回 true

unordered_set::insert 的 second 为 false 时,集合原来已经有该值;这把一次 find 和一次可能的 insert 合并成了一个状态转移。集合不记录次数,因为第二次出现已经足以确定答案,第三次及以后不会被访问。

代码演进

containsBySorting 先复制并排序,再把“全局相等”转成“相邻相等”;排序消除了远距离比较,但付出了建立全序的代价。 containsByHash 不再关心值的相对大小,集合只保存前缀中是否出现过的值。公共入口选哈希版本,因为题目只要求存在性判断, 它不修改输入且期望线性扫描;排序版本保留为输入允许复制或需要确定性排序上界时的替代路线。

代码走读与方案选择

reserve 只是预留容量,减少扫描过程中扩容搬迁,不改变集合的不变量。循环变量保存的是值而不是下标, 因为本题只判断值的存在性;输入引用没有被排序或写回,所以顺序保持不变。

哈希方案的 O(1) 是期望复杂度,极端碰撞时严格最坏情况可能退化。若后续还需要有序数组,或应用场景要求排序带来的确定性 上界,可以复制后排序;若题目进一步要求返回原始下标,则状态不能只保存集合,需要升级为值到位置的映射。

复杂度与边界

每个元素至多一次插入,哈希查找和插入的总时间期望为 O(n),集合额外空间为 O(n);发现重复后会提前停止。 排序替代法为 O(n log n),原地排序会修改输入,复制后排序则需要 O(n) 额外空间。空数组、单元素、负数、零值和多次重复 都由同一个前缀不变量处理,不需要额外分支。