4 sum

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

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

先来一个直接计算的：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # from collections import defaultdicts
        numLen, res, d = len(nums), set(), {}
        if numLen < 4: return []
        nums.sort()
        for p in range(numLen):
            for q in range(p+1, numLen):
                if nums[p]+nums[q] not in d:
                    d[nums[p]+nums[q]] = [(p,q)]
                else:
                    d[nums[p]+nums[q]].append((p,q))
        for i in range(numLen):
            for j in range(i+1, numLen-2):
                T = target-nums[i]-nums[j]
                if T in d:
                    for k in d[T]:
                        if k[0] > j: res.add((nums[i],nums[j],nums[k[0]],nums[k[1]]))
        return [list(i) for i in res]

再来一个能够解决 k sum 的方案，而且速度超级快：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def findNsum(l, r, target, N, result, results):
            if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination
                return
            if N == 2: # two pointers solve sorted 2-sum problem
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]: # remove duplicate
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else: # recursively reduce N
                for i in range(l, r+1):
                    if i == l or (i > l and nums[i-1] != nums[i]):
                        findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)

        nums.sort()
        results = []
        findNsum(0, len(nums)-1, target, 4, [], results)
        return results

上面的参数有点多，可以简化一下，但是速度就慢了：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        def ksum(num, k, target):
            i = 0
            result = set()
            if k == 2:
                j = len(num) - 1
                while i < j:
                    if num[i] + num[j] == target:
                        result.add((num[i], num[j]))
                        i += 1
                    elif num[i] + num[j] > target:
                        j -= 1
                    else:
                        i += 1
            else:
                while i < len(num) - k + 1:
                    newtarget = target - num[i]
                    subresult = ksum(num[i+1:], k - 1, newtarget)
                    if subresult:
                        result = result | set( (num[i],) + nr for nr in subresult)
                    i += 1

            return result

        return [list(t) for t in ksum(nums, 4, target)]

再来一个迭代器版本的, 同样慢：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        def ksum(num, k, target):
            i = 0
            if k == 2:
                j = len(num) - 1
                while i < j:
                    if num[i] + num[j] == target:
                        yield (num[i], num[j])
                        i += 1
                    elif num[i] + num[j] > target:
                        j -= 1
                    else:
                        i += 1
            else:
                while i < len(num) - k + 1:
                    newtarget = target - num[i]
                    for sub in ksum(num[i+1:], k - 1, newtarget):
                        yield (num[i],) + sub
                    i += 1

        return [list(t) for t in set(ksum(nums, 4, target))]

再来一个官网的解法，有点麻烦，但是很好理解，就是转化为3sum，然后2sum：

class Solution:
    def twoSum(self, nums, target, l, r):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        n = len(nums[l : r+1])
        if n < 2:
            return list()

        start = nums[l - 1]
        dict1 = dict()
        ret = list()
        for i in range(l, r+1):
            other = target - nums[i]
            if other in dict1:
                ret.append([start, other, nums[i]])
            dict1[nums[i]] = i

        return ret

    # nums[l...r] 中返回 a+b+c=target
    def threeSum(self, nums, target, l, r):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        n = len(nums[l : r+1])
        if n < 3:
            return list()

        start = nums[l-1]
        ret = list()
        for i in range(l, r+1):
            if nums[i] > 0 and target <= 0:
                break
            if (i >= l+1 and nums[i] == nums[i-1]):
                continue
            ll = self.twoSum(nums, target-nums[i], i+1, r)
            if (ll == list()):
                continue
            for i in ll:
                i.insert(0, start)
                ret.append(i)
        return ret

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n < 4:
            return []
        nums.sort()
        ret = set()
        for i in range(n):
            ll = self.threeSum(nums, target-nums[i], i+1, n-1)
            if ll == list():
                continue
            for l in ll:
                ret.add(tuple(l))
        return list(ret)