3Sum – Python 3 (Week 18 – 10)

class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @return: Find all unique triplets in the array which gives the sum of zero.
    """
    def threeSum(self, numbers):
        # write your code here
        numbers.sort()
        results = []
        length = len(numbers)
        for i in range(length - 2):
            if i > 0 and numbers[i] == numbers[i - 1] or numbers[i] > 0:
                continue
            self.find_two_sum(numbers, i + 1, length - 1, -numbers[i], results)
            
        return results
        
    def find_two_sum(self, numbers, start, end, target, results):
        left, right = start, end
        
        while left < right:
    
            if numbers[left] + numbers[right] == target:
                results.append([-target, numbers[left], numbers[right]])
                left += 1
                right -= 1
                while left < right and numbers[left] == numbers[left - 1]:
                    left += 1
                while left < right and numbers[right] == numbers[right + 1]:
                    right -= 1
            
            elif numbers[left] + numbers[right] > target:
                right -= 1
            else:
                left += 1