王磊
以来2sum的3sum实现,已经在leetcode上通过。
class Solution(object):
def threeSum(self, nums):
nums.sort()
res = []
for i, num in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]:
continue
new_nums = nums[i+1:]
two_sums = self.twoSum(new_nums, -num)
for two_sum in two_sums:
res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
return res
def twoSum(self, nums, target):
d = {}
res = []
hit = False
for i, num in enumerate(nums):
if i > 1 and nums[i] == nums[i-1] and hit:
continue
if num in d:
res.append([d[num], i])
hit = True
else:
d[target - num] = i
hit = False
return res