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为数组长度。