| 链接 | 存在重复元素 II |
|---|---|
| 题序号 | 219 |
| 题型 | 数组 |
| 解法 | 1. 哈希表、2. 滑动窗口 |
| 难度 | 简单 |
| 熟练度 | ✅✅✅✅ |
题目
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，
满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
提示：
1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
题解
- 核心思想：使用哈希表来存储元素及其索引。遍历数组，对于当前元素如果它已经在哈希表中，并且当前索引与哈希表中存储的索引之差小于等于k，则返回true。如果它不在哈希表中，或者索引之差大于k，则更新哈希表中该元素的索引为当前索引。
- 复杂度：时间复杂度和空间复杂度都是O(n)。
- c++ 实现算法：
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> numIndexMap; // 哈希表存储数字及其下标
for (int i = 0; i < nums.size(); i++) {
// 检查当前数字是否在哈希表中，如果不等式为 true，则表示 nums[i] 已经在哈希表中，可能是重复元素
//numIndexMap.find(nums[i])：表示查找哈希表 numIndexMap 中是否包含键值为 nums[i] 的元素。
//如果找到该元素，返回该元素的迭代器。
//如果找不到该元素，返回哈希表的 end() 迭代器。
if (numIndexMap.find(nums[i]) != numIndexMap.end()) {
// 判断下标差值是否小于等于 k，numIndexMap[nums[i]]是键对应的值，即上次该数字在数组中的下标
if (i - numIndexMap[nums[i]] <= k) {
return true;
}
}
// 更新当前数字的最新下标
numIndexMap[nums[i]] = i;
}
return false; // 遍历完仍未找到符合条件的元素
}
- 算法推演：
假设输入为： nums = [1, 2, 3, 1]，k = 3
初始化
定义一个哈希表 numIndexMap，存储数组中每个元素的最近一次出现位置。遍历数组，从第一个元素开始处理。
第 1 步：元素 1（索引 0）
当前元素：nums[0] = 1
哈希表：numIndexMap = {}（空）
1 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0}第 2 步：元素 2（索引 1）
当前元素：nums[1] = 2
哈希表：numIndexMap = {1: 0}
2 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0, 2: 1}第 3 步：元素 3（索引 2）
当前元素：nums[2] = 3
哈希表：numIndexMap = {1: 0, 2: 1}
3 不在哈希表中，将其加入哈希表：numIndexMap = {1: 0, 2: 1, 3: 2}第 4 步：元素 1（索引 3）
当前元素：nums[3] = 1
哈希表：numIndexMap = {1: 0, 2: 1, 3: 2}
1 已经在哈希表中，上次出现的索引为 numIndexMap[1] = 0。检查索引差：3 - 0 = 3，满足条件 ≤k。 返回
true。输出
由于在第 4 步找到了满足条件的元素对，算法返回 true。
- c++ 完整 demo：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> numIndexMap; // 哈希表存储数字及其下标
for (int i = 0; i < nums.size(); i++) {
// 检查当前数字是否在哈希表中，如果不等式为 true，则表示 nums[i] 已经在哈希表中，可能是重复元素
//numIndexMap.find(nums[i])：表示查找哈希表 numIndexMap 中是否包含键值为 nums[i] 的元素。
//如果找到该元素，返回该元素的迭代器。
//如果找不到该元素，返回哈希表的 end() 迭代器。
if (numIndexMap.find(nums[i]) != numIndexMap.end()) {
// 判断下标差值是否小于等于 k，numIndexMap[nums[i]]是键对应的值，即上次该数字在数组中的下标
if (i - numIndexMap[nums[i]] <= k) {
return true;
}
}
// 更新当前数字的最新下标
numIndexMap[nums[i]] = i;
}
return false; // 遍历完仍未找到符合条件的元素
}
int main() {
vector<int> nums = {1, 2, 3, 1};
int k = 3;
cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;
nums = {1, 0, 1, 1};
k = 1;
cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;
nums = {1, 2, 3, 1, 2, 3};
k = 2;
cout << (containsNearbyDuplicate(nums, k) ? "true" : "false") << endl;
return 0;
}
