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

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

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

Solution :

方法2

方法3

ref: 1. CSDN bolg 2. leetcode discussion