0219. Contains Duplicate II¶
题目信息¶
- 题号:
存在重复元素 II
- 难度:
Easy
- 主题:
数组、滑动窗口、哈希索引、下标距离
- 原题:
- 重点:
最近一次出现、窗口过期、边界距离、先查询再更新
题目重述¶
给定整数数组 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++ 实现¶
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <vector>
class Solution {
private:
static bool containsByLastIndex(const std::vector<int>& nums, int k) {
if (k <= 0) return false;
std::unordered_map<int, int> last;
last.reserve(nums.size());
for (int index = 0; index < static_cast<int>(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<int>& nums, int k) {
if (k <= 0) return false;
std::unordered_set<int> window;
const std::size_t capacity = std::min(
nums.size(), static_cast<std::size_t>(k) + 1);
window.reserve(capacity);
for (int index = 0; index < static_cast<int>(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<int>& 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] 时:
若映射存在且
i - last[nums[i]] <= k,最近位置与当前下标组成合法答案,立即返回true;无论是否命中,都把该值的最近位置更新为
i,让未来查询使用更新后的代表;若最近位置已经超过
k,更早位置差值更大,因此被覆盖不会漏掉答案。
查询必须发生在更新之前,否则当前下标会把自己记录成最近出现位置,距离 0 会伪造一个不同下标的匹配。
状态走读¶
对 nums = [1,2,3,1]、k = 2,最近下标状态如下:
当前下标和值 |
查询到的旧位置 |
距离与动作 |
更新后的 |
|---|---|---|---|
|
不存在 |
首次出现,记录 0 |
|
|
不存在 |
首次出现,记录 1 |
|
|
不存在 |
首次出现,记录 2 |
|
|
0 |
距离 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 的重复在查询更新前被正确接受。