今天題目的是要找出3個數字相加為0的所有的組合．而且答案不可以有重複．

問題

https://leetcode.com/problems/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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [ [-1,-1,2] , [-1,0,1] ]

Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

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

提示

通常我們會採用 Set 來避免儲存重複的資料， 而且 Set 佔用的記憶體空間也比 Array 來得小．然而 Python 沒有辦法把 Array 當成資料儲存在 Set 裡，因為 Array 並不是 hashable 的格式．如果要先將 Array 轉成 Tuple 再存進去，又會花更多時間在轉換資料格式上．所以在這一題，我們必須採用別的方式來避免儲存到重複的資料

而且值得一提的是 Go 內建沒有 Set 這個資料格式，只能用 Map 來達到類似的目的．

答案

我將原始資料排序後，透過將此題目轉成 2 Sum，找出 a + b = -c 的方式去解，

class Solution:
    def twoSum(self, nums: List[int], t: int, result: List[List[int]]):
        target = -nums[t]
        i = t+1
        j = len(nums)-1
        while i < j:
            sum = nums[i] + nums[j]
            if sum == target:
                result.append([nums[t], nums[i], nums[j]])
                i += 1
                while i < j and nums[i] == nums[i-1]:
                    i += 1
            elif sum < target:
                i += 1
            else:
                j -= 1

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for t in range(len(nums)-2):
            if t > 0 and nums[t] == nums[t-1]:
                continue
            self.twoSum(nums, t, result)
        return result

Go

import "sort"

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}
    for t := 0; t < len(nums)-2; t++ {
        if t > 0 && nums[t] == nums[t-1] {
            continue
        }
        i := t+1
        j := len(nums)-1
        for i < j {
            sum := nums[i] + nums[j] + nums[t]
            if sum == 0 {
                ans := []int{nums[t], nums[i], nums[j]}
                result = append(result, ans)
                i++
                for i < j && nums[i] == nums[i-1] {
                    i++
                }
            } else if sum < 0 {
                i++
            } else {
                j--
            }
                
        }
    }
    
    return result
}