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

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

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

Solution :

方法2

方法3

ref: 1. CSDN bolg 2. leetcode discussion