0217. Contains Duplicate
========================
题目信息
--------
:题号: 0217. 存在重复元素
:难度: 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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
static bool containsBySorting(std::vector nums) {
std::sort(nums.begin(), nums.end());
for (int index = 1; index < static_cast(nums.size()); ++index) {
if (nums[index] == nums[index - 1]) return true;
}
return false;
}
static bool containsByHash(const std::vector& nums) {
std::unordered_set seen;
seen.reserve(nums.size());
for (int value : nums) {
if (!seen.insert(value).second) return true;
}
return false;
}
public:
bool containsDuplicate(std::vector& nums) {
return containsByHash(nums);
}
};
题解
----
从位置对枚举到值的存在性
~~~~~~~~~~~~~~~~~~~~~~~~~~
最直观的算法枚举每个 ``i < j``,直接比较 ``nums[i]`` 和 ``nums[j]``。它覆盖了全部可能的下标对,所以一定正确,
但长度为 ``n`` 时最坏需要比较 ``n(n-1)/2`` 对,时间复杂度为 ``O(n^2)``;即使很早发现重复,无法改善没有重复时的上界。
排序后,相等值必然相邻,只需检查相邻元素,时间降为 ``O(n log n)``。代价是排序获得了题目没有要求的全序,还可能改变输入;
若必须保留输入顺序,就要先复制数组。
题目真正询问的是“当前值是否曾经出现”,不需要知道旧值的顺序、次数或下标。维护一个哈希集合,把与当前值的所有旧位置
压缩成一个“已出现”状态:一次集合查询就替代了当前值与所有旧位置的重复比较。
方法对比
~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间
- 额外空间
- 被保留或删除的工作
* - 枚举所有位置对
- ``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]``,每次插入的返回值同时告诉我们“是否已见”和“是否需要更新状态”:
.. list-table::
:header-rows: 1
* - 当前值
- 查询前 ``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)`` 额外空间。空数组、单元素、负数、零值和多次重复
都由同一个前缀不变量处理,不需要额外分支。