繼第 12 天的「283. Move Zeroes」，今天來解 217 這題！還沒看過第 12 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/contains-duplicate/

演算法與資料結構

• Array
• Hash Table

題意

給予一個整數陣列，回傳 true 當任何數值出現過兩次。否則回傳 false 。

範例

nums = [1, 2, 3, 1]

1 有出現過兩次，回傳

true

1. Dictionary

直觀的可以用字典來暫存，優點是取用的時候 O(1)

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var hashTable = [Int: Bool]()
        for number in nums {
            if hashTable[number] != nil {
                return true
            } else {
                hashTable[number] = true
            }
        }
        return false
    }
}

執行結果

• Runtime: 623 ms (Beats: 35.94%)
• Memory: 19.5 MB (Beats 20.78%)

複雜度分析

令 n 為陣列的長度

2. Set

當然可以用 Set ，速度上有快一些？

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var hashTable = Set<Int>()
        
        for number in nums {
            if hashTable.contains(number) {
                return true
            } else {
                hashTable.insert(number)
            }
        }
        return false
    }
}

執行結果

• Runtime: 583ms (Beats 72.60%)
• Memory: 18.9MB (Beats 35.87%)

複雜度分析

3. 一行解

更簡化的話可以這樣想：我們只在意數量

因此只要把陣列轉換成 Set 即可比較元素數量，不需要親自走訪：

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        return Set(nums).count != nums.count
    }
}

執行結果

• Runtime: 868 ms (Beats 9.68%)
• Memory: 18.6 MB (Beats 79.22%)

超差。

複雜度分析

令 n 為陣列的長度

比較

在一行解可以看到花了超多時間，送出的時候的確還有等待的空擋。推測是在初始化 Set 的時候花了比較多的計算資源。

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！