-
-
Save humpydonkey/44f7d2b464f2389f3e8d5d5b8d6bf451 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
def threeSum(self, nums: List[int]) -> List[List[int]]: | |
""" | |
Three pointer solution built on top of the two-sum problem. | |
Time: O(n^2) | |
Space: O(1) | |
The trick is how to handle duplicate. The order of checking two pointers' equality matters: one must move pointer first, | |
then check equality against the prior value. The case starting from the prior value included the second case. | |
E.g. -1, 0, 0, 1 | |
0, 0, 1 included the case of 0, 1. But the case starts from the second 0 doesn't include the prior case. | |
""" | |
nums.sort() | |
res = [] | |
n = len(nums) | |
for start in range(n-1): | |
l, r = start+1, n-1 | |
if start > 0 and nums[start] == nums[start-1]: | |
continue # remove duplicates | |
while l < r: | |
if nums[start] + nums[l] + nums[r] == 0: | |
res.append([nums[start], nums[l], nums[r]]) | |
while l < r: | |
l += 1 | |
if nums[l] != nums[l-1]: | |
break | |
while l < r: | |
r -= 1 | |
if nums[r] != nums[r+1]: | |
break | |
elif nums[start] + nums[l] + nums[r] > 0: | |
r -= 1 | |
elif nums[start] + nums[l] + nums[r] < 0: | |
l += 1 | |
return res |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment