題目描述
給出一個有n個整數(shù)的數(shù)組S，在S中找到三個整數(shù)a, b, c，找到所有使得a + b + c = 0的三元組。
在三元組(a, b, c)，要求a <= b <= c，結(jié)果不能包含重復(fù)的三元組。
測試樣例
輸入:[2,7,11,15]
輸出:[]
輸入:[-1,0,1,2,-1,-4]
輸出:[[-1, 0, 1],[-1, -1, 2]]
思路
將三數(shù)之和轉(zhuǎn)換為兩數(shù)之和求解，兩數(shù)之和的目標(biāo)為第三個數(shù)的相反數(shù)。對數(shù)組進(jìn)行排序，然后依次取出一個數(shù)作為固定數(shù)，接著在除這個數(shù)之外的子序列中拿出頭尾兩個數(shù)，將它們之和與目標(biāo)比較，若一致則說明找到解，否則縮減子序列的范圍繼續(xù)查找。
具體步驟
1、由于要求最終生成的每個三元組是升序的，因此可以先將數(shù)組由小到大進(jìn)行排序；
2、若排序后數(shù)組的第一個元素都大于0，說明不可能存在三數(shù)之和為0的情況；
3、否則，遍歷數(shù)組中的每個數(shù)，直到倒數(shù)第3個數(shù)，將其作為a，當(dāng)a不是序列中第一個數(shù)的時候，要先判斷下a是否和位于它前一位的數(shù)相同，若是，則進(jìn)行下一輪循環(huán)；
4、將位于a之后的所有數(shù)中取出首尾兩個數(shù)分別作為b和c；
5、將b+c與0-a進(jìn)行比較，若前者大，則將c前面的一個數(shù)（比c?。┳鳛閏；若后者大，則將b后面的一個數(shù)（比b大）作為b；若兩者相等，則找到一個符合要求的三元組(a, b, c)，記錄下來；
6、在4中若找到解，由于符合要求的三元組不能重復(fù)，因此需要將b向前移動1位和將c向后移動一位。另外，若b和c沒有走到重合的位置，且b和它前一位的數(shù)相同，則b繼續(xù)往前走；若c和它后一位的數(shù)相同，c也繼續(xù)往后走；
7、重復(fù)5、6直至b和c走到重合的位置；
8、重復(fù)3-7直至數(shù)組中倒數(shù)第3個數(shù)也處理完
代碼
class Solution:
? ? """
? ? @param numbers: Give an array numbers of n integer
? ? @return: Find all unique triplets in the array which gives the sum of zero.
? ? """
? ? def threeSum(self, numbers):
? ? ? ? # write your code here
? ? ? ? if not numbers:
? ? ? ? ? ? return []
? ? ? ? # 先進(jìn)行排序
? ? ? ? seq = sorted(numbers)
? ? ? ? # 若序列中的最小數(shù)大于0，
? ? ? ? # 則不可能有三數(shù)之和為0的情況
? ? ? ? if seq[0] > 0:
? ? ? ? ? ? return []
? ? ? ? ans = []
? ? ? ? for i in range(len(seq) - 2):
? ? ? ? ? ? # 去重
? ? ? ? ? ? if i > 0 and seq[i] == seq[i - 1]:
? ? ? ? ? ? ? ? continue
? ? ? ? ? ? a = seq[i]
? ? ? ? ? ? target = 0 - a
? ? ? ? ? ? j, k = i + 1, len(seq) - 1
? ? ? ? ? ? while j < k:
? ? ? ? ? ? ? ? '''去重'''
? ? ? ? ? ? ? ? if j - i > 1 and seq[j] == seq[j - 1]:
? ? ? ? ? ? ? ? ? ? j += 1
? ? ? ? ? ? ? ? ? ? continue
? ? ? ? ? ? ? ? b, c = seq[j], seq[k]
? ? ? ? ? ? ? ? if b + c > target:
? ? ? ? ? ? ? ? ? ? k -= 1
? ? ? ? ? ? ? ? elif b + c < target:
? ? ? ? ? ? ? ? ? ? j += 1
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ans.append([a, b, c])
? ? ? ? ? ? ? ? ? ? '''由于結(jié)果不能包含重復(fù)的三元組，因此b和c的位置需要移動'''
? ? ? ? ? ? ? ? ? ? j += 1
? ? ? ? ? ? ? ? ? ? k -= 1
? ? ? ? ? ? ? ? ? ? '''去重'''
? ? ? ? ? ? ? ? ? ? while j < k and seq[j] == seq[j - 1]:
? ? ? ? ? ? ? ? ? ? ? ? j += 1
? ? ? ? ? ? ? ? ? ? while j < k and seq[k] == seq[k + 1]:
? ? ? ? ? ? ? ? ? ? ? ? k -= 1
? ? ? ? return ans
附：方法2 —— 不需排序，代碼量較少但空間復(fù)雜度更高
思路
實質(zhì)也是將三數(shù)之和轉(zhuǎn)化為兩數(shù)之和。
不同的是，直接遍歷序列中的每個數(shù)，直到倒數(shù)第3個數(shù)，將其作為a，然后遍歷a之后的每個數(shù)，作為b，看看 c = 0 - a - b 是否在之前的遍歷過程中遇到過，若是則說明找到一組解；否則將b記錄下來，這樣，遍歷到后面的b時，此時的b就有可能成為后續(xù)的c = 0 - a - b。
代碼
from collections import defaultdict
class Solution:
? ? """
? ? @param numbers: Give an array numbers of n integer
? ? @return: Find all unique triplets in the array which gives the sum of zero.
? ? """
? ? def threeSum(self, numbers):
? ? ? ? # write your code here
? ? ? ? if not numbers:
? ? ? ? ? ? return []
? ? ? ? ans = []
? ? ? ? for i in range(len(numbers) - 2):
? ? ? ? ? ? a = numbers[i]
? ? ? ? ? ? # b + c = 0 - a
? ? ? ? ? ? target = 0 - a
? ? ? ? ? ? residual = defaultdict(bool)
? ? ? ? ? ? for j in range(i + 1, len(numbers)):
? ? ? ? ? ? ? ? b = numbers[j]
? ? ? ? ? ? ? ? c = target - b
? ? ? ? ? ? ? ? # 把此時的c當(dāng)作以前的b,
? ? ? ? ? ? ? ? # 看是否出現(xiàn)過
? ? ? ? ? ? ? ? if residual.get(c):
? ? ? ? ? ? ? ? ? ? seq = sorted([a, b, c])
? ? ? ? ? ? ? ? ? ? # 不能包含重復(fù)的三元組
? ? ? ? ? ? ? ? ? ? if seq not in ans:
? ? ? ? ? ? ? ? ? ? ? ? ans.append(seq)
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? # 由于結(jié)果不能包含重復(fù)的三元組，
? ? ? ? ? ? ? ? ? ? # 因此是有當(dāng)沒有找到滿足條件的方案時
? ? ? ? ? ? ? ? ? ? # 才把此時的b記錄下來
? ? ? ? ? ? ? ? ? ? residual[b] = True
? ? ? ? return ans
