15. 3Sum
题目:
https://leetcode.com/problems/3sum/
难度:
Medium
第一想法，先把nums排序，用三个loop，无法AC
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
res = []
nums.sort()
for i in range(n):
for j in range(i,n):
for k in range(j,n):
if nums[i] + nums[j] + nums[k] == 0 and j != i and k != j and k != i:
curRes = [nums[i],nums[j],nums[k]]
if curRes not in res:
res.append(curRes)
return res
然后查了一下2sum，用2sum的花样，因为要排除重复以及输出是按照从小到大的输出:
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
nums.sort()
self.res = []
for i in range(n):
self.twoSum(nums[i+1:], 0-nums[i])
return [list(i) for i in self.res]
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
lookup = {}
for num in nums:
if target - num in lookup:
if (-target ,target - num, num) not in self.res:
self.res.append((-target ,target - num, num))
lookup[num] = target - num
