# 217 Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

題目是要判斷nums陣列裡是否有重複的值。是有重複就回傳true，沒有重複就回傳false

參考別人的想法，別人用hashmap的思維來解這題會快很多，超過99.99%人的解法。但可能不好理解，首先要先判斷nums陣列是否是null或nums長度是否為1。第二是用nums[X]的值當index存入新的陣列t，當t[x] == 1時回傳true，不然就令t[x] = 1，但為縮小t陣列長度，最好先取得原來nums陣列裡的min、max。這樣t的長度就可以new int[max -min +1] 達到t陣列大小是nums陣列裡的最大值+1的長度。避免nullpointexception發生。全部只花費差不多1ms， Memory Usage: 42 MB

程式碼:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums == null || nums.length < 2){
            return false;
        }
        int min = nums[0];
        int max = nums[0];
        for(int i : nums){
            if(i<min){
                min = i;
            }
            if(i>max){
                max = i;
            }
        }
        
        int[] t = new int[max - min +1];
        for(int ii: nums){
            if(t[ii-min] == 1){
                return true;
            }else{
                t[ii-min] = 1;
            }
        }
        return false;
    }
}

還有用Arrays.sort()的方式去完成的，超過95%的解法。時間複雜度在5ms，空間複雜度在 Memory Usage: 41.8 MB

程式碼:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i =1 , j = nums.length-1 ; i<=nums.length/2 ; i++, j--){
            if(nums[i] == nums[i-1] || nums[j] == nums[j-1]){
                return true;
            }
        }
        return false;
    }
}

我自已是用hashset去解這題，但只有超過68%的人解法。不用一開始去判斷nums是否為null或nums長度是否為1，但要用if(myHashSet.contains(i))來判斷是否重複，但實際上可以不用這個if判斷式，利用hashset不可以存重複值的特性，也可以完成相同的。

class Solution {
    public boolean containsDuplicate(int[] nums) {
         Set<Integer> myHashSet = new HashSet<>();
        for(Integer ii: nums){
            if(myHashSet.contains(ii)){
                return true;
            }
            myHashSet.add(ii);
        }
        return false;
    }
}

不用在foreach裡一直判斷的程式碼:

class Solution {
    public boolean containsDuplicate(int[] nums) {
         Set<Integer> myHashSet = new HashSet<>();
        for(Integer ii: nums){
            myHashSet.add(ii);
        }
        return myHashSet.size() != nums.length;
    }
}

以上2者時間複雜度是一樣的。都是8ms，空間複雜度在 Memory Usage: 42 MB