15. 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]
]
Solution: Two Pointers
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
three_sums = []
pre = None
for idx, num in enumerate(nums):
if num == pre:
continue
pre = num
low = idx + 1
high = len(nums) - 1
while low < high:
three_sum = num + nums[low] + nums[high]
if three_sum < 0:
low += 1
elif three_sum > 0:
high -= 1
else:
three_sums.append([num, nums[low], nums[high]])
while low < high and nums[low] == nums[low + 1]:
low += 1
while low < high and nums[high] == nums[high - 1]:
high -= 1
low += 1
high -= 1
return three_sums