4 Sum

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.

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
given array S = [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]
]

思路：
n重循环这里就不做赘述了，而且可能会引起超时，肯定不是出题者的本意，这里使用hash表来实现。

  1. 将问题转化为3sum，即我们可以将两个元素求和之后当做一个元素处理。首先建立一个字典dict，字典的key值为数组中每两个元素的和，每个key对应的value为这两个元素的下标组成的元组。
  2. 接下来就转化为3sum的问题，有一些细节仍需要处理，我们需要找到满足的value。
  3. 根据value找到对应的下标，判断下标是否和当前遍历元素的下标重复。不重复则将结果添加至结果集中。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def fourSum(self, nums, target):
        nums_len, res, dict = len(nums), set(), {}
        if nums_len < 4: return []
        nums.sort()
        # 将值添加至至dict
        for i in range(nums_len):
            for j in range(i+1, nums_len):
                if nums[i]+nums[j] not in dict:
                    dict[nums[i]+nums[j]] = [(i,j)]
                else:
                    dict[nums[i]+nums[j]].append((i,j))
        # 查找Value   
        for i in range(nums_len):
            for j in range(i+1, nums_len-2):
                V = target-nums[i]-nums[j]
                if V in dict:
                    for k in dict[V]:
                        if k[0] > j: res.add((nums[i],nums[j],nums[k[0]],nums[k[1]]))
        return [list(i) for i in res]