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`` 的重复在查询更新前被正确接受。