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)):
add = [nums[i]]+two[j]
add.sort()
if add not in res:
res.append(add)
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:
visited.add(nums[i])
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)