3Sum
Given an array S of n integers, are there elements a, b, c in S 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.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
前两个解法，思路上大同小异，都是很直接的方法，但并不是最优解：
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) <= 2:
return []
ret = []
tar = 0
num.sort()
i = 0
while i < len(num) - 2:
j = i + 1
k = len(num) - 1
while j < k:
if num[i] + num[j] + num[k] < tar:
j += 1
elif num[i] + num[j] + num[k] > tar:
k -= 1
else:
ret.append([num[i], num[j], num[k]])
j += 1
k -= 1
# folowing 3 while can avoid the duplications
while j < k and num[j] == num[j - 1]:
j += 1
while j < k and num[k] == num[k + 1]:
k -= 1
while i < len(num) - 2 and num[i] == num[i + 1]:
i += 1
i += 1
return ret
上面的方法，略麻烦，还是看下caikehe的简化写法：
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 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
再来一个排序然后二分法的：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if not nums: return []
count = {}
for n in nums: count[n] = count.get(n, 0) + 1
ans = []
if 0 in count and count[0] >= 3:
ans.append([0,0,0])
nums = sorted(count)
for i,n in enumerate(nums):
if not n: continue
if count[n] >= 2:
comp = -2*n
if comp in count and comp != n:
ans.append([n]*2 + [comp])
if n < 0:
left = bisect.bisect_left(nums, -n - nums[-1], i+1)
right = bisect.bisect_right(nums, -n // 2, left)
for j in nums[left:right]:
comp = -n - j
if comp in count and comp != j:
ans.append([n,j,comp])
return ans
如果是这类问题，还是推荐这里的最优解，是将3sum的问题转化为2sum的问题：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 创建一个存储结果的列表
res = []
# 创建一个字典用于存储nums中的元素及其出现的次数
d = dict()
for i in nums:
d[i] = d.get(i, 0) + 1
# 创建两个列表分别用于存储正数和负数
posnum = [i for i in d if i > 0]
negnum = [i for i in d if i < 0]
# 如果nums中全为0，则返回0；
if d.get(0, 0) > 2:
res.append([0, 0, 0])
if negnum == [] or posnum == []:
return res
# 分别对正数和负数两个列表中的值进行判断
for i, x in enumerate(posnum):
if d[x] >= 2 and -2 * x in d:
res.append([x, x, -2 * x])
for y in posnum[i + 1:]:
if -(x + y) in d:
res.append([x, y, -x - y])
for i, x in enumerate(negnum):
if d[x] >= 2 and -2 * x in d:
res.append([x, x, -2 * x])
for y in negnum[i + 1:]:
if -(x + y) in d:
res.append([x, y, -x - y])
# 三个数之中有一个数为0 的情况
if 0 in d:
for x in posnum:
if -x in d:
res.append([x, 0, -x])
return res
