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)`` 额外空间。空数组、单元素、负数、零值和多次重复 都由同一个前缀不变量处理,不需要额外分支。