3Sum
- 3 min read
- Array
- Sorting
- Blind75
- LC-Medium
- Two Pointers
3 years ago
Approach 1: Sort & 2Sum
- Array is sorted to prevent counting duplicate triplets.
- The outer loop is used to iterate through the array, the value of which is denoted by the variable
a. - 2Sum is used to find the remaining number in the triplet, denoted by the variables
bandc. - For each number
a, we need to find the remaining 2 numbersbandcsuch thata + b + c = 0. - During 2Sum, we should not stop once a solution is found because alternate solutions are still possible inside the remaning subarray.
- When a solution is found, we should still account for duplicates, and hence, we should skip the duplicate numbers both for
landr.
def threeSum(nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]: continue
l, r = i + 1, len(nums) - 1
while l < r:
b, c = nums[l], nums[r]
sum_ = a + b + c
if sum_ == 0:
ans.append([a, b, c])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r: l += 1
while nums[r] == nums[r + 1] and r > l: r -= 1
elif sum_ < 0: l += 1
else: r -= 1
return ans
What if you cannot sort/modify/duplicate the array?
Use a hashset approach. Put a combination of three sorted values into a hashset to avoid duplicates. Two hashsets. One for storing duplicates, one for storing the answers.
The hashset used to store duplicates, called dups, is needed to skip duplicates in the beginning. When we're allowed to sort the array, this issue is taken care of, but here we can't, so we use a hashset.
This is basically extended two sum. Asymptotically, time complexity is the same as the previous solution. But this is worse since we're not checking for duplicates on the other side. We cannot, since the array is not sorted. To overcome this, we only store sorted triplets in our ans.
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans, dups = set(), set()
for i, a in enumerate(nums):
if a not in dups:
dups.add(a)
seen = set()
for j, b in enumerate(nums[i + 1:]):
diff = -a - b
if diff in seen:
ans.add(tuple(sorted((a, b, diff))))
seen.add(b)
return ans