https://leetcode.com/problems/3sum/
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:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)
Code
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums or len(nums) < 3:
return []
res = []
nums.sort()
for i in xrange(len(nums)-2):
if i > 0 and nums[i-1] == nums[i]:
continue
target = -nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] == target:
res.append([nums[i], nums[left], nums[right]])
left_val = nums[left]
right_val = nums[right]
left += 1
right -= 1
while left < right and nums[left]==left_val:
left += 1
while right > left and nums[right]==right_val:
right -= 1
elif nums[left] + nums[right] < target:
left = left + 1
else:
right = right - 1
return res
Idea:
You sort the array first in O(nlogn) time. Then you have a pointer `i` starting from 0 and ending at len(nums)-3. The number pointed by `i` denotes the candidate for the first number in a 3sum triplet. You want to run a 2sums algorithm on all elements on the right of `i` with target equal to `-nums[i]`: you create a `left` pointer right next to `i` and a `right` pointer at the end of nums. You move `left` to right or move `right` to left according to `nums[left] + nums[right] ? target`. You should take care of duplication, either for `i` (line 14 -15) and for `left` and `right` (line 27-30)
The time complexity is O(N^2) and space complexity is O(1).
Reference: