0219. Contains Duplicate II ========================== 题目信息 -------- :题号: 0219. 存在重复元素 II :难度: Easy :主题: 数组、滑动窗口、哈希索引、下标距离 :原题: `LeetCode 0219 `_ :重点: 最近一次出现、窗口过期、边界距离、先查询再更新 题目重述 -------- 给定整数数组 ``nums`` 和非负整数 ``k``,判断是否存在两个不同下标 ``i``、``j``,同时满足 ``nums[i] == nums[j]`` 与 ``|i-j| <= k``。值相同但距离超过 ``k`` 的位置对不算答案;只返回布尔值,输入数组不需要修改。 当 ``k=0`` 时,不同下标之间不可能达到距离限制。 自建示例 -------- ``nums = [1,2,3,1]``、``k = 3`` 返回 ``true``:两个 1 的距离正好等于上限。 同一个数组配 ``k = 2`` 返回 ``false``:重复值存在,但唯一的一对距离为 3,不能把全局重复当成局部重复。 ``nums = [1,0,1,1]``、``k = 1`` 返回 ``true``:最后两个 1 相邻;更早的 1 虽然相同,却已经不在当前允许距离内。 C++ 实现 -------- .. code-block:: cpp #include #include #include #include class Solution { private: static bool containsByLastIndex(const std::vector& nums, int k) { if (k <= 0) return false; std::unordered_map last; last.reserve(nums.size()); for (int index = 0; index < static_cast(nums.size()); ++index) { const auto position = last.find(nums[index]); if (position != last.end() && index - position->second <= k) { return true; } last[nums[index]] = index; } return false; } static bool containsByWindow(const std::vector& nums, int k) { if (k <= 0) return false; std::unordered_set window; const std::size_t capacity = std::min( nums.size(), static_cast(k) + 1); window.reserve(capacity); for (int index = 0; index < static_cast(nums.size()); ++index) { if (window.find(nums[index]) != window.end()) return true; window.insert(nums[index]); if (index >= k) window.erase(nums[index - k]); } return false; } public: bool containsNearbyDuplicate(std::vector& nums, int k) { return containsByLastIndex(nums, k); } }; 题解 ---- 从全局存在性到带时间边界的状态 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 直接枚举所有 ``i < j`` 并检查两个条件能保证正确,但最坏需要 ``O(n^2)`` 次比较。只维护“是否出现过”的全局集合又不够, 因为它会把距离很远的重复也报告为成功;为每个值保存全部下标虽然保留了信息,却还要在下标列表中寻找最近的合法位置。 固定当前下标 ``i`` 后,可能与它配对的旧下标只能在闭区间 ``[i-k, i-1]``。更早的位置以后只会离当前及未来下标更远, 所以可以永久删除。状态因此只需要保存活动窗口中的信息,而不必保存整个前缀。 两种等价压缩 ~~~~~~~~~~~~ **最近下标映射**:每个值只保留最近一次出现的位置。对当前值,最近位置最有希望满足距离上限;若最近位置都太远, 更早位置只会更远,全部可以被覆盖。查询与更新都为哈希表期望常数时间。 **显式窗口集合**:保存最近 ``k`` 个历史位置上的不同值。当前值命中集合就说明窗口内存在合法旧下标;处理后删除刚刚离开下一轮窗口的值。 它直接表达窗口不变量,额外空间为 ``O(min(n,k))``,但删除按值成立依赖于“若窗口内已有同值,扫描时已经提前返回”。 主解选择最近下标映射,因为它只保留未来查询真正需要的一个代表,不必维护出入窗口的值集合;显式窗口作为替代方案保留, 用于展示“删除过期状态”和“只覆盖最近代表”这两种压缩视角的差异。 状态定义与转移 ~~~~~~~~~~~~~~ 处理下标 ``i`` 前,``last[value]`` 表示该值在 ``nums[0..i-1]`` 中最后一次出现的下标;不存在的值没有映射。 读取 ``nums[i]`` 时: 1. 若映射存在且 ``i - last[nums[i]] <= k``,最近位置与当前下标组成合法答案,立即返回 ``true``; 2. 无论是否命中,都把该值的最近位置更新为 ``i``,让未来查询使用更新后的代表; 3. 若最近位置已经超过 ``k``,更早位置差值更大,因此被覆盖不会漏掉答案。 查询必须发生在更新之前,否则当前下标会把自己记录成最近出现位置,距离 0 会伪造一个不同下标的匹配。 状态走读 ~~~~~~~~ 对 ``nums = [1,2,3,1]``、``k = 2``,最近下标状态如下: .. list-table:: :header-rows: 1 * - 当前下标和值 - 查询到的旧位置 - 距离与动作 - 更新后的 ``last`` * - ``0:1`` - 不存在 - 首次出现,记录 0 - ``1 -> 0`` * - ``1:2`` - 不存在 - 首次出现,记录 1 - ``1 -> 0, 2 -> 1`` * - ``2:3`` - 不存在 - 首次出现,记录 2 - ``1 -> 0, 2 -> 1, 3 -> 2`` * - ``3:1`` - 0 - 距离 3 大于 2,覆盖旧位置 - ``1 -> 3, 2 -> 1, 3 -> 2`` 最后一个 1 没有命中,说明“值相同”与“距离足够近”必须由同一个位置对同时满足。若把 ``k`` 改为 3,第三行的距离检查就会成功。 代码走读 ~~~~~~~~ 主入口调用 ``containsByLastIndex``,所以代码中的 ``last`` 只保存每个值的最近代表。``find`` 先读取旧位置,条件成立时立即返回; 无论命中与否,``last[nums[index]] = index`` 都把当前位置交给下一轮。这个赋值不是统计次数,而是覆盖已经不如当前位置有用的旧状态。 替代函数 ``containsByWindow`` 则把窗口显式存成集合:先查询当前值,再插入,最后删除过期下标。它没有被公共入口调用, 但展示了同一不变量的另一种实现;主解少维护一个出窗口操作,保留的状态也更小。 最近位置为何足够 ~~~~~~~~~~~~~~~~~~ 设某个值在当前下标 ``i`` 之前出现过的位置依次为 ``p_1 < ... < p_m``。最近位置 ``p_m`` 使 ``i-p_m`` 最小; 若它仍大于 ``k``,所有 ``p_1 ... p_{m-1}`` 都更早、更远,不可能成为答案。若它不大于 ``k``,它本身就是合法配对。 因此保存一个下标已经覆盖了保存全部下标的判定能力。 显式窗口的边界顺序 ~~~~~~~~~~~~~~~~~~~~ 替代函数 ``containsByWindow`` 在处理 ``index`` 时先查询、再插入、最后删除 ``index-k``。当 ``index=k`` 时, 下标 0 与当前下标的距离正好等于上限,必须参加本轮查询;只有查询完成后它才离开下一轮窗口。若提前删除会漏掉边界答案, 若延后一轮删除则会把距离 ``k+1`` 的位置错误保留。主解不显式删除窗口,但用最近位置覆盖实现了同样的“过期状态淘汰”。 复杂度与边界 ~~~~~~~~~~~~ 最近下标法每个元素进行一次哈希查找和一次更新,时间期望为 ``O(n)``,额外空间为不同值数量的 ``O(n)``;严格最坏时间受哈希碰撞影响。 显式窗口法时间期望同样为 ``O(n)``,额外空间为 ``O(min(n,k))``。``k=0`` 直接返回 ``false``;单元素数组没有不同下标, 距离恰好等于 ``k`` 的重复在查询更新前被正确接受。