在两数之和基础上的延伸,核心内容不变,但是要注意特殊情况的预判和逻辑。
1
题目描述
给定一个整数数组nums,判断nums中是否存在三个元素 a,b,c ,使得 a + b + c = 0 。如不存在返回[],如存在返回所有满足条件且不重复的答案。如:输入[-1,0,1,2,-1,-4]返回[[-1,0,-1],[-1,-1,2]],如输入[-3,3],返回[]。
2
解题
本题需有两点预判:1、当数组长度小于3时,直接输出[];2、对数组首先进行排序,如当前数字与前一个相同,所得结果也将一致,直接跳过即可。
思路一:哈希表
本题要找到满足条件的三个元素,当固定第一个元素a,则题目转化成找到b、c使得和为-a的问题,即与LeetCode刷题DAY 8:两数之和中问题一致,因此也可用哈希表的方法解决。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums)<3:
return []
nums = sorted(nums)
a = list()
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
h_map = {}
target = -nums[i]
for j in range(i+1,len(nums)):
if target - nums[j] in h_map:
a.append(sorted([nums[i],nums[j],target-nums[j]]))
h_map[nums[j]]=j
return list(set([tuple(t) for t in a]))
思路二:双指针
当对数组完成排序并固定第一个元素a,则题目与LeetCode刷题DAY 9:两数之和II中问题一致,可用双指针方法解决。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums)<3:
return []
nums = sorted(nums)
a = list()
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
x = i+1
y = len(nums)-1
target = -nums[i]
while x<y:
if nums[x]+nums[y] == target:
a.append(sorted([nums[i],nums[x],nums[y]]))
x += 1
elif nums[x]+nums[y] < target :
x += 1
else:
y -= 1
return list(set([tuple(t) for t in a])