3 Sum

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• Given an array of integers numbers that is sorted in non-decreasing order.
• Return the indices (1-indexed) of two numbers, [index1, index2], such that they add up to a given target number target and index1 < index2. Note that index1 and index2 cannot be equal, therefore you may not use the same element twice.
• There will always be exactly one valid solution.
• Your solution must use  additional space.

Solution

• Initially, a naïve solution would be to brute-force this. However, this would be .
• Instead, we can sort the list, and do a two-pointers solution. This would be

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
	    # time complexity: O(n^2)
	    # space complexity: O(n)
 
        res = []
        nums.sort()
 
        for i, a in enumerate(nums):
            if a > 0:
                break
 
            if i > 0 and a == nums[i - 1]:
                continue
            
            l, r = i + 1, len(nums) - 1
 
            while l < r:
                total = a + nums[l] + nums[r]
 
                if total > 0:
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
        return res

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───