PRoblem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

思路 1. 暴力枚舉法+分類討論法。這種題直接暴力枚舉的話，時間復雜度高達O(n^3)，所以我一開始對暴力枚舉加上了分類討論。三個數之和為0有以下幾種情況：

因此，首先對輸入的數組進行“正數，零，負數”分類，然后再窮舉這四種情況的所有組合。最后發現，時間復雜度仍然接近O(n^3)，這優化意義不大。

#Note: 以下兩種方法是題目“2sum”的延伸。“2sum”求的是：對于輸入的數組，求出兩數之和等于某特定值的所有組合。在這題目“3sum”中，因為題目是求a,b,c使得a+b+c=0，所以我們可以看作是求a,b使得a+b=-c。這樣其實就是窮舉版的“2sum”問題。 2. 借助hash表。對輸入的數組放入一個哈希表中，然后遍歷哈希表的每一個數a，然后調用2sum函數：新建一個用于標記的集合set，遍歷輸入數組的每一個值b（此時要去掉一個數a，因為數具有不可復用性），判斷集合set中是否存在一個數c，使得c = -a-b。如果有，則為目標答案，加到result list中；如果沒有，則把b數加入到集合set中。 這樣做的好處在于減少了一層循環，使得時間復雜度降為O(n^2)，但同時空間復雜度是O(n)。另外，調用2sum函數時，也可以遍歷已建立好的hash表，可以更節省時間。不過需要注意的是要考慮[0，0，0]這種情況。 3. 雙向游標法。首先將輸入數組nums排序，然后遍歷輸入數組的每個數a作為target值，然后調用2sum函數：對于有序數組（除去數a），定義兩個指針指向首尾兩端，即，一個指向nums[0],一個指向num[len(nums)]。然后有如下三種情況： (1) 若當前和小于-a，則左指針右移； (2) 若當前和大于-a，則右指針左移； (3) 若當前和等于-a，則為目標答案。 這里排序的時間復雜度為O(nlogn)，遍歷的時間復雜度為O(n^2)，所以總的時間復雜度近似于O(n^2).

Solution :

方法2

方法3

ref: 1. CSDN bolg 2. leetcode discussion