每天一道算法：四数之和

19、四数之和

题目

给定一个长度为 n 的整数数组，一个目标整数 target。

在数组中找到4个数a,b,c,d，使得 a+b+c+d=target。

要求找到所有不重复的四元组合。

示例：

思路

1、三数之和+外层循环

在三数之和的双指针法的基础上，最外层再多嵌套一层循环即可。

三数之和的双指针法详见。

四数之和的整体架构为：

1、外面双层循环，代表四个数中的前两个数。

2、里面为一首一尾双指针，代表四个数中的后两个数，双指针逐步往中间移动，直至相遇。

2、改进版

改进的关键主要体现在循环之前先通过最小几个数相加和最大几个数相加判断是否有继续嵌套循环的必要。

如果最小几个数相加都大于目标数，或者最大几个数相加都小于目标数，则可以直接跳过。

另外，可以将循环改为递归。使用递归是为了防止代码重复，否则第一层和第二层循环都要加上提前判断的代码。

代码

python实现

扩展

改进版使用递归的另一个好处是，可以不仅仅是4个数相加，任意大于等于3的数相加，都可以用这套代码。