LeetCode Note Java 00217：Contains Duplicate

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 229 所需閱讀時間 ≈ 1 分鐘

判斷輸入的 intArray nums 是否包含重複的數字。

題目

Contains Duplicate Easy

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int tmp = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

直接用雙層迴圈去解，結果超時，只好換個做法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> dic = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (dic.contains(nums[i])) {
                return true;
            }
            dic.add(nums[i]);
        }
        return false;
    }
}

換成 HashSet 當字典的方式就可以通過測試，時間複雜度：O(n)。

重點物件或方法：

  • HashSet

檢討

要盡量避免使用雙層迴圈，但是中間跑去查了 HashSet 怎麼使用，對於這些基本集合還是要熟悉。

看了別人的答案後，發現使用 HeshSet 算是滿普遍的解法。