15. 3Sum — LeetCode(Python)
I got you!
Problem:
Given 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: []Constraints:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
Solution:
nums.sort()
res = []
for i, num in enumerate(nums):
if i > 0 and num == nums[i-1]:
continue
l, r = i+1, len(nums) - 1
while l < r:
threeSum = num + nums[l] + nums[r]
if threeSum < 0:
l += 1
elif threeSum > 0:
r -= 1
else:
res.append([num, nums[l], nums[r]])
l += 1
while nums[l] == nums[l-1] and l < r:
l += 1
return resExplanation —
We use a two-pointer approach here.
First, we sort our list. Then we iterate over the numbers sequentially.
During, each iteration, we initialize two pointers — one on the next index and other at the end of the list.
We then, calculate the sum of nums[i], nums[l] and nums[r].
If this sum is negative, we increment our left pointer since we know that the list is sorted. If it is positive, we decrement our right pointer.
If the sum is equal to zero, we append the list of indices to our answer, and then we shift the left pointer to an index with a new non-repeating element to avoid appending copies in our answer.
The final list is then returned.
Time and Space Complexity —
Sorting the list takes O(nlogn) time and our algorithm requires us to visit each element in the array twice on average, leading us to require quadratic time.
The space complexity depends on our sorting algorithms and can be either linear or constant.
Thus, if n is the length of the array nums,
Time Complexity: O(n²)
Space Complexity: O(1) or O(n)
