#217. Contains Duplicate

題目描述

給你一個整數陣列nums，如果有任何數值出現至少兩次就回傳true，如果每個數字都是單一的則回傳false。

限制條件

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

解題思路

Hash Table

最直覺的方式就是利用雜湊表來記錄數字是否出現過，

public class Solution { 
	public bool ContainsDuplicate(int[] nums) {
        var hs = new HashSet<int>();
        for(int i=0;i<nums.Length;i++){
            if(hs.Contains(nums[i])){
                return true;
            }else{
                hs.Add(nums[i]);
            }
        }
        return false;
    }
}

複雜度分析：

時間複雜度：最糟的情況下要檢查完所有陣列元素，因此時間複雜度為O(n)。
空間複雜度：最糟的情況下要記錄完所有陣列元素，因此空間複雜度為O(n)。

學習重點

雜湊表