第 30 天就來寫算是經典的 3Sum 吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/palindrome-number

題意

請回傳所有 3 個元素加起來和為 0 的組合，這三個元素的索引不能重複，組合也不能重複。

例如，當傳入一個這樣的數組時

 0  1  2  3  4
[0, 0, 0, 0, 0]

只會有一個數組

  0  1  2
[[0, 0, 0]]

思維

跳過已經取用過的數字

先排序再走訪就可以避過相同的數值，每次走訪時，當目前的元素和前一個索引的數值相同時就可以跳過不處裡。

走訪方式

使用三個 pointers

1. 第一個放在最左邊為固定 pointer
2. 第二、三個在第一個指標的右側區間，以左右雙指標的方式移動

程式碼

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        guard nums.count >= 3 else { return [] }
        let nums = nums.sorted(by: <)
        var results: [[Int]] = []
        
        for index in 0..<(nums.count-2) {
            // 跳過有相符的元素
            if index == 0 || nums[index] != nums[index-1] { 
                let target = -nums[index]
                var left = index + 1
                var right = nums.count - 1

                while left < right {
                    let sum = nums[left] + nums[right]
                    if sum == target {
                        results.append([nums[index], nums[left], nums[right]])
                        // 跳過有相符的元素
                        while left < right && nums[left] == nums[left + 1] { left += 1 }
                        while left < right && nums[right] == nums[right - 1] { right -= 1 }
                        left += 1
                        right -= 1
                    } else if sum > target {
                        // 如果太大，就把右指標左移
                        right -= 1
                    } else {
                        // 如果太小，就把左指標右移
                        left += 1
                    }
                }
            }
        }
        return results
    }
}

執行結果

• Runtime: 160 ms (beats 80.60%)
• Memory Usage: 18.7 MB (Beats 51.23%)

複雜度分析

令 n 為陣列的長度

結語

以上，就是今天的 LeetCode in Swift ，如果有什麼問題和回饋歡迎留言一起討論，還有謝謝大家 30 天以來的支持！