0219. Contains Duplicate II

题目信息

题号:
  1. 存在重复元素 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++ 实现

#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] 时:

  1. 若映射存在且 i - last[nums[i]] <= k,最近位置与当前下标组成合法答案,立即返回 true;

  2. 无论是否命中,都把该值的最近位置更新为 i,让未来查询使用更新后的代表;

  3. 若最近位置已经超过 k,更早位置差值更大,因此被覆盖不会漏掉答案。

查询必须发生在更新之前,否则当前下标会把自己记录成最近出现位置,距离 0 会伪造一个不同下标的匹配。

状态走读

对 nums = [1,2,3,1]、k = 2,最近下标状态如下:

当前下标和值

查询到的旧位置

距离与动作

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