2.3　四数之和

题目描述（第18题）

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在4个元素a、b、c、d，使a+b+c+d的值与target相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例

给定数组nums=[1,0,-1,0,-2,2]和target=0。

满足要求的四元组集合为[[-1,0,0,1],[-2,-1,1,2],[-2,0,0,2]]。

解法一　暴力法（超时）

这道题目在三数之和的基础上，数的个数又增加了一个，变成了4个，并且与上一题相比，本题的target不恒等于0。

首先考虑使用暴力法来解决。

思路

一个符合直觉的算法是暴力地将所有的四元组枚举出来，并判断其和是否等于target。唯一需要注意的是去重，比如[-1,0,0,1]和[0,0,-1,1]只能算一个四元组。在这里，使用了序列化数组作为key，四元组作为value的方法，将其保存到hashmap中来达到去重的目的。

这里会用到回溯法，而回溯法的基本思路是，首先固定1个元素，然后固定第2元素……，直到全部元素（在这里是4个元素）确定下来，判断是否满足要求（在这里是不重复且和为target）。如果满足要求，则将其加入结果集；如果不满足要求，则回退一步走其他分支。这种每次面临多个选择，选择其中一个走到头，之后回退到选择点继续其他选择的方法，被称为回溯法。关于回溯法的解题思路可以参考第16章的内容，关于回溯法解题的模板可以参考18.2节的内容。

代码

复杂度分析

●　时间复杂度：时间复杂度取决于组合数，由排列组合原理可知，组合数共有n(n-1)(n-2)(n-3)个，因此时间复杂度为O(n4)个，其中n为数组长度。

●　空间复杂度：由于使用了hashmap来存储所有访问过的组合，因此空间复杂度为O(n4)，其中n为数组长度。

解法二　分治法

上面的算法比较直观，容易想到，直接套模板就可以解，但是有超时的风险，我们来看一下更优的算法。

思路

可以将问题分解为若干子问题，对子问题求解后将解合并即可。具体来看，可以先将四数和four_sum分解为两数和，即twoSum(a,threeSum(A))，其中a是数组中的任意数，A是除a之外的其他数的集合；接下来继续对三数和threeSum进行分解，将其分解为twoSum(b,twoSum(B))。这样就将四数和问题转化为了两数和问题，至此，使用前面讲过的两数和的解法即可解决。

代码

复杂度分析

●　时间复杂度：O(n3)。

●　空间复杂度：本算法的空间消耗主要由tempList、调用栈和排序算法这3块组成。和tempList的空间消耗相比，调用栈及排序算法产生的空间消耗更少，因此空间复杂度为O(n)，其中n为数组长度。