LC 0015 [M] 3Sum - ALawliet/algorithms GitHub Wiki

prereq: 2sum sorted

---

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        
        def search_pairs(i):
            l = i + 1
            r = n - 1

            while l < r: # 2Sum
                s = nums[i] + nums[l] + nums[r]
                diff = target - s

                if diff == 0: # s == 0
                    threes.append( [nums[i], nums[l], nums[r]] )
                    while l < r and nums[l] == nums[l+1]: l += 1
                    while l < r and nums[r] == nums[r-1]: r -= 1
                    l += 1; r -= 1

                elif diff > 0: # too small/go bigger right, s < target
                    l += 1

                elif diff < 0: # too big/go smaller left, s > target
                    r -= 1

        threes = []
        nums.sort()
        target = 0
        
        for i in range(n - (3-1)): # 3 for 3Sum
            if i > 0 and nums[i] == nums[i-1]: continue
                
            search_pairs(i)

        return threes

T: O(n^2)