3 Sum

Question

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Example For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

Note Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

Thoughts

这一题可以借鉴2Sum的算法，加起来为0， 那么取出一个元素i target = -numbers[i], 再用2Sum的方法找

注意点

• 这里要找到所有的unique set
• 要注意去掉重复的，我的办法是将原来的array先sort一下，然后如果当前元素==前一个，就跳过

Solution

class Solution:
    """
    @param numbersbers : Give an array numbersbers 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
        if len(numbers) < 3:
            return None
        numbers.sort()
        results = []
        for idx, num in enumerate(numbers):
            if idx != 0 and num == numbers[idx-1]:
                continue
            target = 0 - num
            #only start with afterward elements
            twoSumResults = self.twoSum(numbers[idx+1:], target)
            if twoSumResults:
               for comb in twoSumResults:
                    #index should start from idx + 1
                    result = [numbers[idx], numbers[comb[0] + idx + 1], numbers[comb[1] + idx + 1]]
                    result.sort()
                    results.append(result)
        return results

    def twoSum(self, numbers, target):
        # need to find all combinations now
        dic = {}
        index1 = None
        index2 = None
        results = []
        found = False
        for idx, num in enumerate(numbers):
            dic[num] = idx
        for idx, num in enumerate(numbers):
            if idx != 0 and num == numbers[idx-1]:
                continue
            t = target - num
            if t in dic and dic[t] > idx:
                found = True
                results.append([idx, dic[t]])

        if not found:
            return None
        return results