15. 3Sum

思路

本題要在給定的陣列當中找出 index 不重複的三個數字使其總和為 0，並且可能會有不只一個組合，要將所有的組合都找出並回傳。本題較為困難的地方在於如果想要使用類似 4Sum II 這題裡以 map 紀錄並查找的話，針對重複計算的部分會變得難以處理，沒辦法用比較直觀的方式來去除重複計算的組合。

因此這裡會採取雙迴圈和雙指標的策略來解決，首先我們需要對原始的陣列進行排序，對於後面處理去除重複的操作時會有很大的幫助。排序好後我們就可以開始遍歷陣列 nums 當中的數字，在一開始我們可以先考慮兩個例外狀況：

nums[i] > 0：由於要找到總和為 0 的組合，加上陣列已經經過排序，不可能在後面找到其他可能的組合，因此遇到這樣的狀況我們就可以直接 break 出去結束迴圈。
nums[i] == nums[i-1]：代表陣列當中有相同的數字，但我們在處理 i-1 的時候已經考慮過所有的情況，所以如果遇到另一個相同的數字的時候就可以直接跳過往下進行。

處理完例外狀況後便可以啟動雙指標來進行搜尋，我們將 left、right 兩個指標放在 i+1 和 len(nums)-1 的位置，並且開始從兩側往中間靠攏，每一輪都會去檢查三個數字的總和 nums[i]+nums[left]+nums[right] 是否為 0，因此會有以下三種可能：

總和 < 0：表示需要更大的數字來讓總和變大，因此將 left++。
總和 > 0：表示需要更小的數字來讓總和變小，因此將 right--。
總和 = 0：找到總和為 0 的組合後將該組合添加到儲存的結果當中，接下來會需要針對 left 和 right 進行去除重複的操作，可以使用如下的方法不斷將 left 的指標往右推，right 也是使用同樣的邏輯進行。

b := nums[left]
for left < right && nums[left] == b {
  left++
}

第二層迴圈則是會在 left 和 right 兩個指標相遇時結束，待第一層迴圈結束後即可回傳結果。

Full Code

Golang

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var results [][]int

	for i := range(nums) {
        a := nums[i]
        if a > 0 {
            break
        }

        if i > 0 && a == nums[i-1] {
            continue
        }

        left, right := i + 1, len(nums) - 1
        for left < right {
            b := nums[left]
            c := nums[right]

            if a + b + c == 0 {
                results = append(results, []int{a, b, c})

                for left < right && nums[left] == b {
                    left++
                }
                for left < right && nums[right] == c {
                    right--
                }
            } else if a + b + c < 0 {
                left++
            } else {
                right--
            }
        }
	}

	return results
}