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.
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: []
Constraints:
0 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
The description was taken from https://leetcode.com/problems/3sum/.
#O(N^2) Time, O(N) Space
class Solution(object):
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
for left in range(0, len(nums)-2):
if left > 0 and nums[left] == nums[left-1]:
continue
mid, right = left+1, len(nums)-1
while mid < right:
three = [nums[left], nums[mid], nums[right]]
three_sum = sum(three)
if three_sum < 0:
mid += 1
elif three_sum > 0:
right -= 1
else:
result.append(three)
mid += 1
right -= 1
while mid < right and nums[mid] == nums[mid-1]:
mid += 1
while mid < right and nums[right] == nums[right+1]:
right -= 1
return resultWe can solve this problem by using a two pointer solution, this solution will be similar to the Two-Sum problem where the input is sorted.
What we will do is sort the array and then iterate through it with a left pointer which will be our anchor. The other two, mid and right pointers will try to find a pair of numbers to sum with the left pointer that will allow the sum of all three to be zero. If the three-sum is too high, we will move the right pointer to a lesser number. If it is too low, we will move the mid pointer to a greater number.
To avoid duplicates, we will just need to check for each pointer, if the current value is the same as the previous and skip it if so.
Let's start by initializing our result and sorting our input.
result = []
nums.sort()
Next, we will begin traversing the array with our left pointer. We only want to go up until two before the end of the array so that we have room to fit in a mid and a right pointer.
for left in range(0, len(nums)-2):
Once our left pointer has gone past the first index and has a previous element, we will check if that element is the same as the current one. If it is, we will skip it so that we don't visit the same number twice.
if left > 0 and nums[left] == nums[left-1]:
continue
Next, we will set our middle and right pointers to one index from the left and the last index of the array respectively.
mid, right = left+1, len(nums)-1
Now, we will begin trying to find a pair of numbers using the mid and right pointers that will sum to the left number in order to sum to zero.
While the pointers haven't overlapped, we still have numbers to consider.
while mid < right:
Let's group these three numbers in an array and calculate the sum.
three = [nums[left], nums[mid], nums[right]]
three_sum = sum(three)
If the three-sum is less than zero, we will move the mid pointer to a greater number.
if three_sum < 0:
mid += 1
If the three-sum is greater than zero, we will move the right pointer to a lesser number.
elif three_sum > 0:
right -= 1
Otherwise, the three-sum is equal to zero, so we will append these three numbers to the result and move both pointers inward to continue searching for numbers that sum with the left pointer to equal zero.
else:
result.append(three)
mid += 1
right -= 1
Before we end the iteration, we will want to make sure we handle duplicates.
If the pointers haven't overlapped and either pointer has the same number that we just moved it from, we will skip the current number it is at because we already accounted for it.
Since we moved the numbers before checking the previous number, we can ensure we won't get an index out of bounds.
while mid < right and nums[mid] == nums[mid-1]:
mid += 1
while mid < right and nums[right] == nums[right+1]:
right -= 1
Once we have finished collecting each three-sum, we will return the result.
return result