題目
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
解法思路（一）
- 外層循環(huán)游標(biāo)
i在[0, nums.length - 1)間遍歷吩翻，內(nèi)層循環(huán)在[i + 1, k]間遍歷嫩痰，暴力解法益缎，當(dāng)然可以乎赴，只不過時間復(fù)雜度是 O(N*K)；
O(N) 時間復(fù)雜度的解法
- 在遍歷開始前入挣，把滑動窗口中
k個元素先存入一個查找表递惋，由于窗口中的元素有可能是重復(fù)的访惜，所以使用 HashMap 統(tǒng)計(jì)窗口中每個元素出現(xiàn)的頻次； - 當(dāng)游標(biāo)
i在遍歷[0, nums.length - 1)的時候宙址，只需要 O(1) 的時間就可以在nums[i]對應(yīng)的窗口中判斷出是否有與其相等的元素轴脐；
解法實(shí)現(xiàn)（一）
時間復(fù)雜度
- O(N)；
空間復(fù)雜度
- O(K)抡砂；
關(guān)鍵詞
滑動窗口 哈希表 HashMap 元素可能重復(fù)的查詢表 窗口滑動的邊界判斷
實(shí)現(xiàn)細(xì)節(jié)
- 對
k >= nums.length這個邊界的判斷大咱，nums.length指向數(shù)組最后一個元素的后面，是數(shù)組外的位置注益，如果k的范圍超過數(shù)組的邊界碴巾，那么滑動窗口就縮小為最長到數(shù)組的邊界nums.length - 1； - 至于
k的精確語義丑搔，根據(jù)題目中給的例子可以確定厦瓢；
package leetcode._219;
import java.util.HashMap;
public class Solution219_1 {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> windowK = new HashMap();
for (int i = 1; i <= (k >= nums.length ? nums.length - 1 : k); i++) {
if (windowK.containsKey(nums[i])) {
windowK.put(nums[i], windowK.get(nums[i]) + 1);
} else {
windowK.put(nums[i], 1);
}
}
for (int i = 0; i < nums.length - 1; i++) {
if (windowK.containsKey(nums[i])) {
return true;
} else if(i + k + 1 < nums.length){
if (windowK.containsKey(nums[i + k + 1])) {
windowK.put(nums[i + k + 1], windowK.get(nums[i + k + 1]) + 1);
} else {
windowK.put(nums[i + k + 1], 1);
}
}
if (windowK.containsKey(nums[i+1])) {
windowK.put(nums[i + 1], windowK.get(nums[i + 1]) - 1);
if (windowK.get(nums[i + 1]) == 0) {
windowK.remove(nums[i + 1]);
}
}
}
return false;
}
public static void main(String[] args) {
// int[] arr = {1, 2, 3, 1}; int k = 3;
// int[] arr = {1, 0, 1, 1}; int k = 1;
// int[] arr = {1, 2, 3, 1, 2, 3}; int k = 2;
int[] arr = {1}; int k = 1;
// int[] arr = {99, 99}; int k = 2;
boolean result = (new Solution219_1()).containsNearbyDuplicate(arr, k);
System.out.println(result);
}
}
解法思路（二）
- 解法思路（一）是“找自己”的元素“追著”窗口跑，解法思路（二）是“找自己”的元素“領(lǐng)著”窗口跑低匙；
解法實(shí)現(xiàn)（二）
時間復(fù)雜度
- O(n)旷痕；
空間復(fù)雜度
- O(k)；
關(guān)鍵字
哈希表 HashSet
k 的幾何意義
- “找自己”的元素最多在距離自己第 k 個的位置“找到自己”顽冶；
- 滑動窗口的長度是
k欺抗；
關(guān)于滑動窗口
- 滑動窗口的長度是
k； - 滑動窗口的起點(diǎn)是“找自己”的后一個元素强重；
- 滑動窗口的終點(diǎn)是距“找自己”第
k遠(yuǎn)的元素绞呈； - 如果滑動窗口被撐到最長贸人，也沒能在其中找到“自己”，那么就要縮短滑動窗口佃声，讓距“找自己”第
k個元素“出離”滑動窗口艺智，并將“找自己”的元素納入滑動窗口，與滑動窗口右鄰接的元素成為新的“找自己”的元素圾亏；
關(guān)于滑動窗口中的元素為什么可以用 HashSet 盛裝
- 滑動窗口的長度最大為
k十拣，滑動窗口被撐到最大只有當(dāng)滑動窗口中沒有相等的元素，如果滑動窗口在沒有被撐到最大的時候志鹃，出現(xiàn)了一個滑動窗口中有的元素想進(jìn)入滑動窗口夭问，那它是進(jìn)不去的，因?yàn)樗呀?jīng)找到了“自己”曹铃，算法運(yùn)行結(jié)束缰趋；
package leetcode._219;
import java.util.HashSet;
// 219. Contains Duplicate II
// https://leetcode.com/problems/contains-duplicate-ii/description/
// 時間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(k)
public class Solution219_2 {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums == null || nums.length <= 1)
return false;
if(k <= 0)
return false;
HashSet<Integer> record = new HashSet<Integer>();
for(int i = 0 ; i < nums.length; i ++){
if(record.contains(nums[i]))
return true;
record.add(nums[i]);
if(record.size() == k + 1)
record.remove(nums[i-k]);
}
return false;
}
private static void printBool(boolean b){
System.out.println(b ? "True" : "False");
}
public static void main(String[] args) {
int[] nums = {1, 2, 1};
int k = 1;
printBool((new Solution219_2()).containsNearbyDuplicate(nums, k));
}
}
