138 lines
2.7 KiB
Markdown
138 lines
2.7 KiB
Markdown
|
||
## 题目地址
|
||
https://leetcode.com/problems/contains-duplicate-ii/description/
|
||
|
||
## 题目描述
|
||
|
||
|
||
```
|
||
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
|
||
|
||
Example 1:
|
||
|
||
Input: nums = [1,2,3,1], k = 3
|
||
Output: true
|
||
Example 2:
|
||
|
||
Input: nums = [1,0,1,1], k = 1
|
||
Output: true
|
||
Example 3:
|
||
|
||
Input: nums = [1,2,3,1,2,3], k = 2
|
||
Output: false
|
||
|
||
```
|
||
|
||
## 思路
|
||
|
||
由于题目没有对空间复杂度有求，用一个hashmap 存储已经访问过的数字即可,
|
||
每次访问都会看hashmap中是否有这个元素，有的话拿出索引进行比对，是否满足条件（相隔不大于k），如果满足返回true即可。
|
||
|
||
|
||
## 关键点解析
|
||
|
||
无
|
||
|
||
|
||
## 代码
|
||
|
||
* 语言支持：JS，Python，C++
|
||
|
||
Javascript Code:
|
||
|
||
```js
|
||
/*
|
||
* @lc app=leetcode id=219 lang=javascript
|
||
*
|
||
* [219] Contains Duplicate II
|
||
*
|
||
* https://leetcode.com/problems/contains-duplicate-ii/description/
|
||
*
|
||
* algorithms
|
||
* Easy (34.75%)
|
||
* Total Accepted: 187.3K
|
||
* Total Submissions: 537.5K
|
||
* Testcase Example: '[1,2,3,1]\n3'
|
||
*
|
||
* Given an array of integers and an integer k, find out whether there are two
|
||
* distinct indices i and j in the array such that nums[i] = nums[j] and the
|
||
* absolute difference between i and j is at most k.
|
||
*
|
||
*
|
||
* Example 1:
|
||
*
|
||
*
|
||
* Input: nums = [1,2,3,1], k = 3
|
||
* Output: true
|
||
*
|
||
*
|
||
*
|
||
* Example 2:
|
||
*
|
||
*
|
||
* Input: nums = [1,0,1,1], k = 1
|
||
* Output: true
|
||
*
|
||
*
|
||
*
|
||
* Example 3:
|
||
*
|
||
*
|
||
* Input: nums = [1,2,3,1,2,3], k = 2
|
||
* Output: false
|
||
*
|
||
*
|
||
*
|
||
*
|
||
*
|
||
*/
|
||
/**
|
||
* @param {number[]} nums
|
||
* @param {number} k
|
||
* @return {boolean}
|
||
*/
|
||
var containsNearbyDuplicate = function(nums, k) {
|
||
const visited = {};
|
||
for(let i = 0; i < nums.length; i++) {
|
||
const num = nums[i];
|
||
if (visited[num] !== undefined && i - visited[num] <= k) {
|
||
return true;
|
||
}
|
||
visited[num] = i;
|
||
}
|
||
return false
|
||
};
|
||
```
|
||
|
||
Python Code:
|
||
|
||
```python
|
||
class Solution:
|
||
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
|
||
d = {}
|
||
for index, num in enumerate(nums):
|
||
if num in d and index - d[num] <= k:
|
||
return True
|
||
d[num] = index
|
||
return False
|
||
```
|
||
C++ Code：
|
||
```C++
|
||
class Solution {
|
||
public:
|
||
bool containsNearbyDuplicate(vector<int>& nums, int k) {
|
||
auto m = unordered_map<int, int>();
|
||
for (int i = 0; i < nums.size(); ++i) {
|
||
auto iter = m.find(nums[i]);
|
||
if (iter != m.end()) {
|
||
if (i - m[nums[i]] <= k) {
|
||
return true;
|
||
}
|
||
}
|
||
m[nums[i]] = i;
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|