3 SUM
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.
Example:
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
My first solution
Set one number and use to node to move, but this method is Time limited. The time consuming is N square plus NlogN.
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
length = len(nums)
nums.sort()
res = []
for i in range(length-2):
if nums[i] > 0: break
if i >= 1 and nums[i] == nums[i-1]:
continue
p = i + 1
q = length - 1
while p != q:
s = nums[i] + nums[p] + nums[q]
if s == 0:
if [nums[i],nums[p],nums[q]] not in res:
res.append([nums[i],nums[p],nums[q]])
p += 1
elif s > 0:
q -= 1
else:
p += 1
return res
My second solution
Use the code of 2Sum.
近期评论