leetcode.219. 存在重複元素 II---哈希（集合）

219. 存在重複元素 II

給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 絕對值 至多為 k。

示例 1:

輸入: nums = [1,2,3,1], k = 3
輸出: true
示例 2:

輸入: nums = [1,0,1,1], k = 1
輸出: true
示例 3:

輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false
           

題解：

• 我們建立一個

  HashSet

  集合即可，接着将nums裡的資料依次放入，并且随着放入的同時我們還要進行contains判讀是否存在重複的元素，且由于題目的要求，我們需要将定義的集合

  維護成一個長度為k的表

  ，即前面的元素需要在長度超過k時在周遊的同時删去，這樣才能維護一個

  不含有重複元素的長度為k的表

  。

代碼：

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set set = new HashSet();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}
}
           

上面使用

HashSet

集合解決，其實并不必須使用

存儲不可重複資料的HashSet

類集合，我們也可以使用

ArrayList

類集合，因為每次周遊使用contains判斷其實就已經維護了我們想要的不含重複元素了。但是使用

ArrayList

需要注意兩點：

1. 關于是否自動裝箱的問題；

因為

ArrayList

有兩個remove方法，一個參數為下标，一個參數為元素對象，是以這裡直接set.remove(nums[i - k]); 會被認為

按照下标

删除，因為能不自動裝箱就不自動裝箱；

1. 逾時；

因為

ArrayList

的contains方法是從頭開始一個一個的使用equals比較，而

HashSet

是直接利用哈希值定位目标位置，是以後者明顯效率更快；

• 并且在使用集合進行存儲資料時一定要注意，jdk5.0之後才有的包裝類的自動裝箱和自動拆箱，且：

代碼：

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        ArrayList set = new ArrayList();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(new Integer(nums[i - k]));
            }
        }
        return false;
    }
}