55 lines
2.1 KiB
Python
55 lines
2.1 KiB
Python
def threeSum(nums):
|
|
"""
|
|
:type nums: List[int]
|
|
:rtype: List[List[int]]
|
|
"""
|
|
# Always end at net zero from the sum
|
|
# first = 0
|
|
# endpoint = len(nums)-1
|
|
# solutionSets = []
|
|
|
|
# # Handle edge-case of small list with only 3 variables
|
|
# if len(nums) == 3 and sum(nums) == 0:
|
|
# solutionSets.append(nums)
|
|
# return solutionSets
|
|
|
|
# while first != len(nums)-2:
|
|
# for i in range(first+1, len(nums)):
|
|
# if nums[first] + nums[i] + nums[endpoint] == 0 and [nums[first], nums[i], nums[endpoint]] not in solutionSets:
|
|
# solutionSets.append([nums[first], nums[i], nums[endpoint]])
|
|
# else:
|
|
# endpoint -= 1
|
|
# first += 1
|
|
# return solutionSets
|
|
|
|
# Solution
|
|
nums.sort()
|
|
answer = []
|
|
|
|
# Loop through until the last triplet, solution relies on negative indexes
|
|
for i in range(len(nums) - 2):
|
|
if nums[i] > 0: # end the loop if the values are positive
|
|
break
|
|
if i > 0 and nums[i] == nums[i-1]: # skip the current i index if it's the same as the last one
|
|
continue
|
|
l = i + 1 # Begin the left index at i + 1
|
|
r = len(nums) - 1 # Begin the right index at the end
|
|
while l < r:
|
|
total = nums[i] + nums[l] + nums[r]
|
|
if total < 0: # If the total is negative, we increase the negative side to get closer to 0
|
|
l += 1
|
|
elif total > 0: # If the total is positive, we decrease the positive side to get closer to 0
|
|
r -= 1
|
|
else:
|
|
triplet = [nums[i], nums[l], nums[r]]
|
|
answer.append(triplet)
|
|
while l < r and nums[l] == triplet[1]: # Continue increasing the left index until a different
|
|
l += 1 # number is found to avoid duplicates
|
|
while l < r and nums[r] == triplet[2]: # Same with decreasing the right index
|
|
r -= 1
|
|
return answer
|
|
|
|
print(threeSum([-1,0,1,2,-1,-4]))
|
|
print(threeSum([0,0,0]))
|
|
print(threeSum([0,0,0,0]))
|
|
print(threeSum([1,2,-2,-1])) |