15. 3Sum
Category: /leetcodeGiven an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
Solution:
- Two pointers
# generalize it to any target
def threeSum(nums):
return _threeSum(nums, 0)
def _threeSum(nums, target):
nums.sort()
res = []
i = 0
while i < len(nums):
tuples = twoSum(nums, i+1, target - nums[i])
for tuple in tuples:
res.append([nums[i]] + tuple)
while i < len(nums) and nums[i] == nums[i+1]:
i += 1
return res
def twoSum(nums, start, target):
lo, hi = start, len(nums)
res = []
while lo < hi:
left, right = nums[lo], nums[hi]
sum = left, right
if sum < target:
while lo < hi and nums[lo] == left: lo += 1
elif sum > target:
while lo < hi and nums[hi] == right: hi -= 1
else: # found a pair
res.append([left, right])
while lo < hi and nums[lo] == left: lo += 1
while lo < hi and nums[hi] == right: hi -= 1
return res
There can be follow up:
4-sum or 100-sum.
