給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
??[-1, 0, 1],
??[-1, -1, 2]
]
解法 1
暴力法，分三層遍歷每個元素 i、j、x，并查找是否存在 i + j + x = target 的目標元素，若存在則加入結(jié)果數(shù)組，注意每層遍歷開始和結(jié)束的位置。
def three_sum(nums):
if len(nums) < 3:
return []
nums.sort()
res = set()
for i in range(0, len(nums) - 2):
for j in range(i + 1, len(nums)-1):
for x in range(j+1,len(nums)):
if nums[i]+nums[j]+nums[x]==0:
res.add((nums[i],nums[j],nums[x]))
return list(map(list, res))
時間復(fù)雜度：， 對于每個元素，都需要遍歷數(shù)組來尋找它所對應(yīng)的目標元素，這將耗費
的時間。因此 3 個元素需要三層遍歷，時間復(fù)雜度為
空間復(fù)雜度：， 用于存放結(jié)果的數(shù)組不超過
個元素。
解法 2
首先對輸入數(shù)組排序，方便去重。第一、第二個元素通過兩層遍歷得到，分別是 v 和 x，判斷哈希表 d 中是否存在符合條件的第三個元素，即 0 - v - x，若不存在則將當(dāng)前元素 x 存入哈希表 d，這里有個優(yōu)化手段是，當(dāng) v 和上一個元素相等時，則直接忽略，避免重復(fù)計算，也達到了結(jié)果數(shù)組去重的目的。注意每層遍歷開始和結(jié)束的位置。
def three_sum(nums):
if len(nums) < 3:
return []
nums.sort()
res = set()
for i, v in enumerate(nums[:-2]):
if i >= 1 and v == nums[i - 1]:
continue
d = {}
for x in nums[i + 1:]:
if -v - x in d:
res.add((v, x, -v - x))
else:
d[x] = 1
return list(map(list, res))
執(zhí)行用時 :724 ms
內(nèi)存消耗 :17.2 MB
時間復(fù)雜度：， 我們對包含
個元素的列表進行了兩層遍歷，時間復(fù)雜度為
。哈希表查詢操作為
，所以時間復(fù)雜度為
。
空間復(fù)雜度：， 空間復(fù)雜度取決于哈希表中存儲的元素數(shù)量，該表中存儲了
個元素。
解法 3
首先對輸入數(shù)組排序，然后對數(shù)組遍歷得到第一個元素，第二、第三個元素采用雙指針分別在頭尾進行搜索，如果三個元素之和小于目標值，則將頭指針向右移動，由于數(shù)組已排序，向右移動即可得到值更大的元素；如果三個元素之和大于目標值，則將尾指針向左移動，得到更小的元素，直到兩個指針相遇，即可查找到當(dāng)前循環(huán)中所有三數(shù)之和等于目標值的元素。這里有兩個優(yōu)化手段，當(dāng) i 和 i + 1 相等時，直接跳過 i + 1，避免重復(fù)計算；當(dāng)頭指針和右側(cè)元素相等時，或者尾指針和左側(cè)元素相等時，也直接跳過，避免重復(fù)計算，這也達到了結(jié)果數(shù)組去重的目的。
def three_sum(nums):
if len(nums) < 3:
return []
nums.sort()
res = []
for i in range(0, len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
sum = nums[i] + nums[l] + nums[r]
if sum > 0:
r -= 1
elif sum < 0:
l += 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return res
執(zhí)行用時 :1164 ms
內(nèi)存消耗 :16.6 MB
時間復(fù)雜度：， 為了確定第一個元素，我們對包含
個元素的列表進行了一層遍歷，為了確定第二、第三個元素，又在第一層遍歷中通過雙指針再次遍歷，時間復(fù)雜度為
。哈希表查詢操作為
，所以時間復(fù)雜度為
。
空間復(fù)雜度：， 用于存放結(jié)果的數(shù)組不超過
個元素。
