15. 3Sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        solution = []
        length = len(nums)-1
        nums.sort()                             

        for i in range(length-1):
            if i > 0 and nums[i] == nums[i-1]:  
                continue
            j = i+1
            k = length
            while j < k:
                temp = nums[i] + nums[j] + nums[k]
                if temp == 0:
                    solution.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    j += 1
                    k -= 1
                elif temp < 0:
                    j += 1
                else:
                    k -= 1
        return solution



class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i == 0 or nums[i] != nums[i-1]:
                low = i+1
                high = len(nums)-1
                target = 0- nums[i]
                while low < high:
                    if nums[low] + nums[high] == target:
                        res.append([nums[i], nums[low], nums[high]])
                        while low < high and nums[low] == nums[low+1]:
                            low+=1
                        while low < high and nums[high] == nums[high-1]:
                            high-=1
                        
                        low+=1
                        high-=1
                    elif nums[low] + nums[high] > target:
                        high-=1
                    else:
                        low +=1
        return res
                        
      
      
      
      class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i - 1] != nums[i]:
                self.twoSum(nums, i, res)
        return res

    def twoSum(self, nums: List[int], i: int, res: List[List[int]]):
        seen = set()
        j = i + 1
        while j < len(nums):
            complement = -nums[i] - nums[j]
            if complement in seen:
                res.append([nums[i], nums[j], complement])
                while j + 1 < len(nums) and nums[j] == nums[j + 1]:
                    j += 1
            seen.add(nums[j])
            j += 1