ThreeSum
- 2 min read
- LC-Easy
- Sliding Window
3 years ago
Solution
- Sliding window solution.
- Builds upon Two Sum II
- Basically, two for loops instead of worser solution which uses 3 for loops
- Remember, if we are to use the principles of two sum II, we need to sort the array first.
- In the outer for loop, we just iterate through the array as normal. Remember we have to not include duplicates, so if i > 0 and the current number nums[i] === nums[i - 1], don't continue since we've already seen this number.
- And then, in the inner for loop, we perform two sum sorted.
- When a solution is found, we need to remember to exclude duplicates. So what we would do is move the left pointers forward if the next number is the same as the previous number.
- We don't have to move the right pointer back because it will be handled by the condition
elif sum_ > 0: k -= 1in the next iteration. In the next iteration, the sum will be greater than the target, and that will cause the right pointer to automatically move left. Why will it be greater than the target? Because we just found a valid solution, and when we move the left pointer to remove duplicates, our sum is obviously going to increase. This means on the next iteration, our right pointer will move back automatically. - REMEMBER: The condition for shifting the pointers to avoid duplicates always checks with the element before, NOT THE ELEMENT AFTER.
- WHY?
- It throws away the first of each group and only ever fixes the last, which both misses valid triplets (e.g.
[0,0,0]) and still can generate duplicates.
| Time | Space | Explanation |
|---|---|---|
O(nlogn + n^2) | O(?) | Space depends on sorting algorithm |
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
triplets = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, len(nums) - 1
while j < k:
sum_ = nums[i] + nums[j] + nums[k]
if sum_ < 0:
j += 1
elif sum_ > 0:
k -= 1
else:
triplets.append([nums[i], nums[j], nums[k]])
j += 1
while j < k and nums[j] == nums[j - 1]:
j += 1
return triplets