求和系列题目
链接
https://leetcode-cn.com/problems/3sum/
题目
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
题目解析
方法一
暴力求解，3 重循环，时间复杂度 O(n^3)
方法二
把 3 重循环中的一重变成查找哈希表，时间复杂度为 O(n^2)。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
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 x not in d:
d[-v - x] = 1
else:
res.add((v, -v - x, x))
return list(map(list, res))
方法三
先排序，然后先遍历第一重循环，剩下的两重循环可以用求两数之和的两头逼近法。
时间复杂度为 O(n^2)。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
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
start = i + 1
end = len(nums) - 1
while start < end:
if v + nums[start] + nums[end] == 0:
res.add((v, nums[start], nums[end]))
start += 1
end -= 1
elif v + nums[start] + nums[end] > 0:
end -= 1
else:
start += 1
return list(map(list, res))
