tags: 15. 3Sum

15. 3Sum 筆記

題目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

思路

題目two sum衍伸過來的, 可以先拿來練習一下

Two Sum

Leetcode必刷題, 每個人的標配 :D
固定一個值, 找出有沒有剩下的數符合

for i in 0..<total-1 {
    for j in i+1..<total {
        if list[i] + list[j] == target {
            return [list[i], list[j]]
        }
    }
}

3Sum

回到3Sum, 這題是要找出任意三個數相加會為0的所有組合, 會出現多組答案的情況, 需要把Two sum的思路改一下
剛開始也是固定一個數, 找出剩下兩個數相加為remain, 就會是符合的組

但因為剩下的值相加不會限縮, 又題目沒有規定說要按順序吐出
所以可以先sort完再處理

拿[-1,0,1,2,-1,-4]作為範例：

let list = nums.sort()
/// [-4,-1,-1,0,1,2]

再來是固定頭, 因為最後一定會至少有兩個數在後面, 所以頭只需要到count - 3

for i in 0..<list.count-2 {
    let remain = -list[i]
    
    // find tuples which sum up with reamin = 0
    ...
}

找出剩下的數組可以用Two Sum的雙迴圈來處理, 但有更好的方法
這時候剛開始sort的用處就出現了

當remain 為-1 如果剩餘的兩個相加 > 1我們就可以停止找數組, 直接換到下一個頭, 在往右加都會是更大

這邊可以用binary search的方式來找, 相加太多就限縮, 太少就往右增加

var left = i + 1, right = list.count - 1
while left < right {
    let sum = remain + nums[left] + nums[right]
    if sum == 0 {
        result.append([nums[i], nums[left], nums[right]])
        left += 1 // 這組可以, 往右推進找下一組答案

        /// 避免找到重複的
        while nums[left] == nums[left - 1], left < right {
            left += 1
        }
    } else if sum > 0 {
        right -= 1
    } else {
        left += 1
    }
}

最後再把上下結合, 就可以解出答案

let nums = nums.sorted()
let total = nums.count - 1
var result = [[Int]]()

for i in 0 ..< nums.count - 2 {
    /// 如果頭都是同一個, 就不用再找避免重複
    if i > 0, nums[i] == nums[i - 1] {
        continue
    }

    var left = i + 1, right = total
    while left < right {
        let sum = nums[i] + nums[left] + nums[right]
        if sum == 0 {
            result.append([nums[i], nums[left], nums[right]])
            left += 1

            while nums[left] == nums[left - 1], left < right {
                left += 1
            }
        } else if sum > 0 {
            right -= 1
        } else {
            left += 1
        }
    }
}

return result

複雜度

• 時間複雜度：O(n^2)
  最外面的那層需要跑n-2次
  裡面的雙指標基本上都會跑完, 但數量會被頭的位置限縮
  平均為n/2 (全跑的話)
  => (n-2) * n/2 = O(n^2)
• 空間: O(n)

延伸問題

• 如果像是4Sum問題, 該怎麼處理呢？
• 5Sum? 6Sum? …