Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

這道題是之前那道Contains Duplicate 包含重復值的延伸，不同之處在于那道題只要我們判斷下數組中是否有重復值，而這道題限制了數組中只許有一組重復的數字，而且他們坐標差不能超過k。那么我們首先需要一個哈希表，來記錄每個數字和其坐標的映射，然后我們需要一個變量d來記錄第一次出現重復數字的坐標差。由于題目要求只能有一組重復的數字，所以我們在遇到重復數字時，首先判斷d是否已經存了值，如果d已經有值了，說明之前有過了重復數字，則直接返回false即可。如果沒有，則此時給d附上值。在網上看到有些解法在這里就直接判斷d和k的關系然后返回結果了，其實這樣是不對的。因為題目要求只能有一組重復數，就是說如果后面又出現了重復數，就沒法繼續判斷了。所以正確的做法應該是掃描完整個數組后在判斷，先看d有沒有存入結果，如果沒有，則說明沒出現過重復數， 返回false即可。如果d有值，再跟k比較，返回對應的結果。OJ的test case沒有包含所有的情況，比如當nums = [1, 2, 3, 1, 3], k = 3時，實際上應該返回false，但是有些返回true的算法也能通過OJ。個人認為正確的解法應該入下：

class Solution { public:bool containsNearbyDuplicate(vector<int>& nums, int k) {map<int, int> m;for (int i = 0; i < nums.size(); ++i) {if (m.find(nums[i]) != m.end() && i - m[nums[i]] <= k) return true;else m[nums[i]] = i;}return false;} };
其他：

思路分析：這題比較簡單，可以直接定義一個長度最大為k的滑動窗口，用一個set維護窗口內的數字判斷是否出現重復，使用兩個指針start和end標記滑動窗口的兩端，初始都是0，然后end不斷進行擴展，掃描元素判斷是否出現重復元素，直到發現end-start>k, 就開始移動start，并且在set中移除對應的元素。如果以為掃描到數組末尾還沒有發現重復元素，那就可以返回false。時間復雜度和空間復雜度都是O（N）。

public class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {//0842Set<Integer> appearedNum = new HashSet<Integer>();int start = 0, end = 0;for(int i = 0; i < nums.length; i++){if(!appearedNum.contains(nums[i])){appearedNum.add(nums[i]);end++;} else return true;if(end - start > k) {appearedNum.remove(nums[start]);start++;}}return false;//0848} }

class Solution { public:bool containsNearbyDuplicate(vector<int>& nums, int k) {map<int, int> buf;int n = nums.size();for (int i = 0; i < n; i++){if (buf.find(nums[i]) != buf.end() && i-buf[nums[i]] <= k){return true;}else{buf[nums[i]] = i;}}return false;} };

總結

以上是生活随笔為你收集整理的Contains Duplicate II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。