# 15. 3Sum
"""
given an integer array 'nums', return all the triplets '[nums[i], nums[j],
nums[k]]' such that 'i != j', 'i != k', 'j != k', and 'nums[i] + nums[j] +
nums[k] == 0'. notice that the solution set must not contain duplicate
triplets
"""
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
ans = []
if len(nums) < 3:
return ans
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, len(nums) - 1
while j < k:
total_sum = nums[i] + nums[j] + nums[k]
if total_sum > 0:
k -= 1
elif total_sum < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
prev_j, prev_k = nums[j], nums[k]
while j < k and nums[j] == prev_j:
j += 1
while j < k and nums[k] == prev_k:
k -= 1
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.threeSum(nums=[-1, 0, 1, 2, -1, -4]))
print(obj.threeSum(nums=[0, 1, 1]))
print(obj.threeSum(nums=[0, 0, 0]))
