15. 3Sum

1.

class Solution:  
    def twoSum(self, nums: List[int], l: int, r: int, target: int) -> List[List[int]]:
        ans = []
        while l < r:
            if nums[l] + nums[r] > target:
                r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                ans.append([nums[l], nums[r]])
                r -= 1
                l += 1
        return list(ans)

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums = sorted(nums)
        ans = set()
        i = 0

        while i < len(nums) - 2:
            j, k = i+1, len(nums)-1
            ts = self.twoSum(nums, j, k, -nums[i])
            ans |= {(nums[i], item[0], item[1]) for item in ts}
            i += 1

        return [list(i) for i in ans]

2.

class Solution:  
    def twoSum(self, nums: List[int], l: int, r: int, target: int) -> List[List[int]]:
        ans = []
        while l < r:
            if nums[l] + nums[r] > target:
                r -= 1
                while l < r and nums[r] == nums[r+1]:
                    r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
                while l < r and nums[l] == nums[l-1]:
                    l += 1
            else:
                ans.append([nums[l], nums[r]])
                r -= 1
                l += 1
                while l < r and nums[r] == nums[r+1]:
                    r -= 1
                while l < r and nums[l] == nums[l-1]:
                    l += 1
        return list(ans)

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums = sorted(nums)
        ans = []
        i = 0

        while i < len(nums) - 2 and nums[i] <= 0:
            j, k = i+1, len(nums)-1
            ts = self.twoSum(nums, j, k, -nums[i])
            ans += [[nums[i], item[0], item[1]] for item in ts]
            i += 1
            while i < len(nums) and nums[i] == nums[i-1]:
                i += 1

        return ans