LeetCode 219. 存在重复元素 II

📌 题目描述

题目级别：简单

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

• 示例 1:
  输入：nums = [1,2,3,1], k = 3
  输出：true

💡 破题思路：哈希表记录最近出现的位置

要在数组中寻找距离不超过 k 的相同元素，最直观的办法就是记录每一个数字上一次出现时的下标。
当我们扫描到当前的元素 nums[i] 时：

1. 去哈希表里查一下，这个数字之前在什么地方出现过（假设下标为 prev_index）。
2. 如果之前出现过，并且满足 i - prev_index <= k，说明我们找到了符合条件的两个索引，直接返回 true。
3. 如果没出现过，或者距离超出了 k，我们就把当前的最新下标更新进哈希表里，继续前进。

⚠️ 极客避坑点（下标 0 的歧义）：
在 C++ 中，std::map 或 unordered_map 在访问不存在的键时，默认会返回 0。
如果直接存入原始下标 i，那么当索引为 0 的元素被存入时，其记录值为 0。这会导致后续代码无法区分“这个元素在下标 0 出现过”和“这个元素从未出现过（默认值 0）”。
作者的惊艳解法：存入时统一使用 i + 1，而判断距离时使用 i + 1 - mp[nums[i]] <= k。这样完美的 0 就成了“未出现”的专属标志，极其高明！

💻 C++ 代码实现 (原汁原味作者版)

class Solution {
public:
    // 💡 工程安全提示：如果将 map 声明为类成员变量，在 LeetCode 连续多测时可能污染数据。
    // 标准工业级写法建议将其定义在函数局部。
    map<int, int> mp;
    
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); i ++ )
        {
            // 作者真实的 Debug 日志痕迹
            cout << mp[nums[i]] << endl;
            
            // 如果该元素之前出现过，且当前下标与上一次出现位置的距离 <= k
            if (mp[nums[i]] && i + 1 - mp[nums[i]] <= k) return true;
            
            // 巧妙存入 i + 1，避开默认值 0 的歧义
            mp[nums[i]] = i + 1; 
        }

        return false;
    }
};