219、Contains Duplicate II
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
思路：
这题是217题的变形，多加了在k范围内重复才返回true，思路也是使用map来做，遍历的同时查重，时间复杂度O(N),空间复杂度为O(N),使用滑动窗口的思想可以优化空间复杂度为O(K)。
代码：
java：
代码语言：javascript复制class Solution {
// solution 1 hashmap. time: O(n) space: O(n)
/*public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) return false;
HashMap<Integer, Integer> map = new HashMap();
for (int i = 0; i < nums.length; i ) {
Integer index = map.get(nums[i]);
if (index != null && i-index <= k){
return true;
}
map.put(nums[i], i);
}
return false;
}*/
// solution 2 Sliding Window. time: O(n) space: O(k)
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums == null || nums.length == 0) return false;
HashSet<Integer> set = new HashSet();
for (int i = 0; i < nums.length; i ) {
if (!set.add(nums[i])) {
return true;
}
// 更新set，保证大小不超过k
if (i >= k) {
set.remove(nums[i - k]);
}
}
return false;
}
} // best casego：
代码语言：javascript复制/*func containsNearbyDuplicate(nums []int, k int) bool {
if nums == nil || len(nums) == 0 { return false }
var (
maps = make(map[int]int)
window = make([]int, 0)
)
for i, v := range nums {
if _, ok := maps[v]; ok{
return true
} else {
maps[v] = i
window = append(window, v)
}
// update map size if we have more than k
if (i >= k) {
delete(maps, window[0])
window = window[1:]
}
}
return false
}
//bad case */
func containsNearbyDuplicate(nums []int, k int) bool {
exist := make(map[int]int, len(nums))
for i, v := range nums{
if pos, ok := exist[v]; ok && i - pos <= k{
return true
}
exist[v] = i
}
return false
}```
