## Description

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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


## Solutions

### 1. 暴力-Two Sum 的解法

之前作为 Two Sum 的题目，用哈希表或者集合来存查找的数，于是将 Three Sum 通过固定一个数值的方式转换成 Two Sum 的题目求解，结果 TLE 了。

from typing import List
import collections
# Time: O(n^2)
# Space: O(n)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
n = len(nums)
res = []
for i in range(n):
two = self.twoSum(nums[:i]+nums[i+1:], -nums[i])
for j in range(len(two)):
return res

def twoSum(self, nums, target):
if not nums:
return []
n = len(nums)
visited = set()
res = []
for i in range(n):
if target-nums[i] in visited:
res.append([target-nums[i], nums[i]])
else:
return res


### 2. 排序+双指针

可以先将数组排序，然后从左到右遍历每一个数，在这个数右边使用双指针从两边往中间选两个数，看加和是否合乎要求，如果不是就按照跟目标数值的大小关系，动态调整左右指针。

# Time: O(n^2)
# Space: O(n)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums) <= 2:
return []
n = len(nums)
res = []
nums.sort()
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, n - 1
while l < r:
_sum = nums[l] + nums[i] + nums[r]
if _sum == 0:
res.append([nums[l], nums[i], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l-1]:
l += 1
while l < r and nums[r] == nums[r+1]:
r -= 1
elif _sum < 0:
l += 1
else:
r -= 1
return res
# 313/313 cases passed (960 ms)
# Your runtime beats 55.05 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.2 MB)