leetcode15 -- 3Sum

# 小郑之家~

### 题目

Given an array nums of n integers, are there elements a, b, c in nums 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:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]



### 解答

class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

nums.sort()

ret = []

if len(nums) ==0 or nums[0]>0 or nums[-1] <0:
return []

for k in range(len(nums)):
if nums[k]>0:
break

if k>0 and nums[k]==nums[k-1]:
continue

target = 0-nums[k]

i = k+1
j = len(nums)-1

while i<j:
summ = nums[i]+nums[j]
if summ==target:
ret.append([nums[k],nums[i],nums[j]])

while i<j and nums[i]==nums[i+1]:
i+=1
while i<j and nums[j]==nums[j-1]:
j -= 1

i += 1
j -= 1
elif summ<target:
i += 1
else:
j -= 1

return ret



 while i<j and nums[i]==nums[i+1]:
i+=1
while i<j and nums[j]==nums[j-1]:
j -= 1