4 Sum

Question

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

Thoughts

与3 sum一样的思路 O(n^3)

Solution

class Solution:
    """
    @param numbersbers : Give an array numbersbersbers of n integer
    @param target : you need to find four elements that's sum of target
    @return : Find all unique quadruplets in the array which gives the sum of 
              zero.
    """
    def fourSum(self ,numbers, target):
        # write your code here
        if len(numbers) < 3:
            return []
        numbers.sort()
        results = []
        for j, n in enumerate(numbers):
            #j from 0, escape duplicates
            if j != 0 and n == numbers[j-1]:
                continue
            if j > len(numbers) - 4:
                break
            threeSumTarget = target - n
            for idx in range(j+1, len(numbers) - 2):
                num = numbers[idx]
                #idx from j + 1, escape duplicates
                if idx != (j+1) and num == numbers[idx-1]:
                    continue
                if idx > len(numbers) - 3:
                    break
                twoSumTarget = threeSumTarget - num
                #only start with afterward elements
                twoSumResults = self.twoSum(numbers[idx+1:], twoSumTarget)
                if twoSumResults:
                   for comb in twoSumResults:
                        #index should start from idx + 1
                        result = [n, num, 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