0219. 存在重复元素 II
题目地址(219. 存在重复元素 II)
题目描述
1
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
2
3
4
5
示例 1:
6
7
输入: nums = [1,2,3,1], k = 3
8
输出: true
9
示例 2:
10
11
输入: nums = [1,0,1,1], k = 1
12
输出: true
13
示例 3:
14
15
输入: nums = [1,2,3,1,2,3], k = 2
16
输出: false
Copied!
前置知识
- hashmap
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
用一个 hashmap 存储已经访问过的数字，每次访问都查看 hashmap 中是否有这个元素，有的话拿出索引进行比对，是否满足条件（相隔不大于 k），如果满足返回 true 即可。
可以看出，这道题就是两数和的进阶版。大家可以将这两道题结合起来理解哦~
公司
- airbnb
- palantir
关键点解析
- 空间换时间
代码
- 语言支持：JS，Python，C++, Java
Javascript Code:
1
/**
2
* @param {number[]} nums
3
* @param {number} k
4
* @return {boolean}
5
*/
6
var containsNearbyDuplicate = function (nums, k) {
7
const visited = {};
8
for (let i = 0; i < nums.length; i++) {
9
const num = nums[i];
10
if (visited[num] !== undefined && i - visited[num] <= k) {
11
return true;
12
}
13
visited[num] = i;
14
}
15
return false;
16
};
Copied!
Python Code:
1
class Solution:
2
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
3
d = {}
4
for index, num in enumerate(nums):
5
if num in d and index - d[num] <= k:
6
return True
7
d[num] = index
8
return False
Copied!
C++ Code：
1
class Solution {
2
public:
3
bool containsNearbyDuplicate(vector<int>& nums, int k) {
4
auto m = unordered_map<int, int>();
5
for (int i = 0; i < nums.size(); ++i) {
6
auto iter = m.find(nums[i]);
7
if (iter != m.end()) {
8
if (i - m[nums[i]] <= k) {
9
return true;
10
}
11
}
12
m[nums[i]] = i;
13
}
14
return false;
15
}
16
};
Copied!
Java Code:
1
class Solution {
2
public boolean containsNearbyDuplicate(int[] nums, int k) {
3
Map<Integer, Integer> map = new HashMap<>();
4
for(int i=0;i<nums.length;i++)
5
{
6
if(map.get(nums[i]) != null && (i-map.get(nums[i])) <= k)
7
{
8
return true;
9
}
10
map.put(nums[i], i);
11
}
12
return false;
13
}
14
}
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago