存在重复元素Ⅱ
· 8 min read
力扣面试经典——219题
💡 参考代码：
/**
* 判断数组中是否存在两个不同的索引 i 和 j，
* 满足 nums[i] == nums[j] 且 abs(i - j) <= k
*
* @param nums 整数数组
* @param numsSize 数组长度
* @param k 限制索引差值的整数
* @return 如果存在满足条件的两个索引返回true，否则返回false
*/
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
// 边界条件检查：数组长度小于等于1或k小于等于0时，不可能存在满足条件的两个不同索引
if (numsSize <= 1 || k <= 0) return false;
// 遍历数组找出最大值和最小值，用于确定计数数组的大小
int max = nums[0], min = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] > max) max = nums[i]; // 更新最大值
if (nums[i] < min) min = nums[i]; // 更新最小值
}
// 创建计数数组，大小为值域范围，用于记录滑动窗口内各元素出现次数
int range = max - min + 1; // 计算值域范围
int* count = (int*)calloc(range, sizeof(int)); // 初始化计数数组，所有元素初始为0
if (!count) return false; // 检查内存分配是否成功，失败则返回false
// 使用双指针维护滑动窗口，left为窗口左边界，right为窗口右边界
int left = 0, right = 0;
while (right < numsSize) {
// 右指针向右扩展，将当前元素加入窗口，对应计数器加1
count[nums[right] - min]++;
// 当窗口大小超过k时，需要收缩左边界以维持窗口大小不超过k+1
while (right - left > k) {
// 将窗口左侧元素移出窗口，对应计数器减1
count[nums[left] - min]--;
left++; // 左指针右移，收缩窗口
}
// 检查当前元素在窗口中是否已存在（计数大于1表示存在重复）
if (count[nums[right] - min] > 1) {
free(count); // 释放动态分配的内存
return true; // 找到满足条件的重复元素，返回true
}
right++; // 右指针右移，扩展窗口
}
// 遍历完成未找到满足条件的重复元素，释放内存并返回false
free(count);
return false;
}
📖 总结：
点击展开题目总结
🤔 存在重复元素 II
1️⃣ 题目核心信息
🎯 功能描述：判断数组中是否存在两个不同的索引 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k
即
- 在数组里找到两个一模一样的数字
- 这两个数字在数组中的位置不能太远（距离不能超过k）
- 如果能找到这样的数字对，就返回true；找不到就返回false
📥 输入输出：
- 输入：
nums: 整数数组k: 限制索引差值的整数
- 输出：如果存在满足条件的两个索引返回 true，否则返回 false
2️⃣ 实现原理
💡 核心思路：使用滑动窗口技术结合计数数组来高效查找在指定距离内的重复元素
📋 实现步骤：
- 首先遍历数组找出最大值和最小值，确定元素值域范围
- 创建大小为值域范围的计数数组，用于记录窗口内各元素出现次数
- 使用双指针维护一个大小不超过 k+1 的滑动窗口
- 遍历数组扩展右边界，同时维护窗口大小不超过 k
- 每次扩展后检查当前元素在窗口中是否已存在（计数>1）
- 若存在则返回 true，遍历结束未找到则返回 false
3️⃣ 关键点解析
原始思路采用双重循环，时间复杂度为 O(n×min(k,n))，在 k 较大时效率低下。优化后的滑动窗口解法通过维护一个大小为 k+1 的窗口，将时间复杂度降低到 O(n)。
🎯 代码技巧
- 使用计数数组代替哈希表，在元素值域较小时提高访问效率
- 双指针技术维护滑动窗口大小，避免重复遍历
- 预处理找出值域范围，节省空间开销
- 及时释放动态分配的内存
4️⃣ 使用场景
✅ 适用情况：
- 在固定窗口大小内查找重复元素
- 元素值域相对较小且连续的情况
- 对时间复杂度要求较高的场景
⚠️ 前提条件：
- 数组长度大于等于1
- k值非负
- 元素值域不能过大（否则空间开销过大）
5️⃣ 复杂度分析
-
⏱️ 时间复杂度：O(n)，其中 n 是数组长度，只需遍历数组两次
-
💾 空间复杂度：O(max - min + 1)，取决于数组元素的值域范围
6️⃣ 注意事项
🚩 边界情况：
- 数组只有一个元素
- k值为0的情况
- 数组中没有重复元素
- 所有元素都相同的情况
💥 易错点：
- 忘记释放动态分配的内存
- 没有正确维护窗口大小导致超出k的限制
- 未考虑元素值域过大导致的空间浪费
- 没有处理内存分配失败的情况
7️⃣ 补充说明
假设输入为：nums = [1, 2, 3, 1, 2, 3], k = 2
执行步骤详解
初始化阶段
numsSize = 6,k = 2- 遍历数组找出最值：
min = 1,max = 3 - 计算值域范围：
range = max - min + 1 = 3 - 创建计数数组：
count[3] = {0, 0, 0}(对应值1,2,3) - 初始化双指针：
left = 0,right = 0
逐步执行过程
步骤1：right = 0, nums[0] = 1
count[1-1]++→count[0] = 1- 检查窗口大小：
right - left = 0 <= k，无需收缩 - 检查重复：
count[0] = 1，不大于1 right++→right = 1
步骤2：right = 1, nums[1] = 2
count[2-1]++→count[1] = 1- 检查窗口大小：
right - left = 1 <= k，无需收缩 - 检查重复：
count[1] = 1，不大于1 right++→right = 2
步骤3：right = 2, nums[2] = 3
count[3-1]++→count[2] = 1- 检查窗口大小：
right - left = 2 <= k，无需收缩 - 检查重复：
count[2] = 1，不大于1 right++→right = 3
步骤4：right = 3, nums[3] = 1
count[1-1]++→count[0] = 2- 检查窗口大小：
right - left = 3 > k，需要收缩 - 收缩窗口：
count[nums[0]-1]--→count[0] = 1left++→left = 1
- 再次检查窗口大小：
right - left = 2 <= k，停止收缩 - 检查重复：
count[0] = 2，大于1 → 返回 true
关键点说明
- 窗口维护：始终保持窗口大小不超过
k+1 - 计数机制：通过
count数组记录窗口内各元素出现次数 - 高效查找：数组索引访问比哈希表更快
- 动态调整：当窗口过大时自动收缩左侧边界
这个例子中，虽然元素1在索引0和3处重复，但由于k=2的限制（索引差为3），实际在滑动窗口算法中，当处理到索引3时会先收缩窗口，使得索引0的元素被移出窗口，因此不会产生匹配。如果k≥3，则会返回true。
通俗解释
核心思想：用一个"移动的窗口"来检查重复
想象一下你在看一排房子，但是你只能通过一个宽度固定的"窗户"来观察，这个窗户一次只能看到k+1个房子。你需要移动这个窗户来检查里面有没有重复的房子号码。
具体步骤：
1. 准备工作
- 先看看这排房子里的号码范围是多少（最大号和最小号）
- 准备一个"计数本"，用来记录当前窗户里每个号码出现了几次
2. 滑动检查过程
想象你拿着这个固定大小的窗户从左往右移动：
第一步：窗户慢慢变大
数组：[1, 2, 3, 1]，k = 2
窗户大小最多是3个位置
位置0：[1] // 窗户里只有1个元素
位置1：[1, 2] // 窗户里有2个元素
位置2：[1, 2, 3] // 窗户里有3个元素，达到最大
第二步：窗户开始滑动
位置3：需要加入数字1，但窗户满了
所以先把最左边的元素踢出去，再加入新元素
[2, 3, 1] // 踢走1，加入1（注意是不同的1）
3. 检查重复 每次往窗户里放新数字时，立即检查：
- 这个数字在当前窗户里是不是已经存在？
- 如果存在（计数>1），那就找到了答案！
生活化比喻：
想象你在玩一个"记忆游戏"：
- 你有一个大小固定的"记忆盒子"，最多能记住k+1个数字
- 你从左到右依次看数组中的数字
- 每看到一个新数字，你就检查：
- 这个数字我是不是在记忆盒子里记过？
- 如果记过，说明找到了"距离很近的相同数字"！
- 如果没记过，就把它放进记忆盒子
- 当记忆盒子满了，就要把最早记住的数字忘掉，给新数字腾位置
加载评论中...