四数之和
预备知识:
最好先看一下前面写的二数之和 和 三数之和 的解法，再来看这个会比较连贯好理解一点。
题目描述：
输入一个长度大于4的，整数类型的数组，和一个target（目标和）。求出这个list中有多少种组合，每种组合应该包含四个数字，这四个数字的和是16，并返回这些组合包含的数字。
例子：
输入： array = [7, 6, 4, -1, 1, 2], target = 16
输出：[[7, 6, 4, -1], [7, 6,1, 2]]
解题思路：
这道题最简单的解题思路：
用 四个 for 循环去遍历数组，求出所有的可能性，将结果对应位16的数组放入result数组中然后返回
暴力解法的时间复杂度是O(n^4)，因为需要遍历四次数组。
接下来介绍另一种解法：
这种解法的思路是：将四数之和降低成二数之和
例如：
在 [7, 6, 4, -1, 1, 2] 这里list中我们可以把这些元素分成两个为一组的组合，例如我们第一个循环拿到7，嵌套的循环循环剩下的数字6，4，-1，1，2。我们可以得到 [7, 6], [7, 4], [7, -1], [7, 1]，[7, 2]，这样题目就好像退化成了二数之和。
首先我们先按在二数之和里面的思路去做，先把第一次循环得出来的组合放入到一个hash table中（python中是用dictionary），key是一对组合的结果，value就是一对组合 {13：[7,6]} , 同时我们得考虑两个数加和等于13的可能性有很多，所以value的部分我们得用二维数组，也就是{13：[[7,6]]}。剩下的元素在hash table 中是 { 13：[[7, 6]], 11: [[7, 4]], 6: [[7, -1]], 8: [[7, 1]]，9: [[7, 2]] }, 我们把这个字典的名字命名为allPairSums意思就是所有组合的和。
上面的思路简单总结一下：循环得出组合，组合结果和target做差值，查看差值是否在 字典 中，如果字典中存在对应的差值，就将两对组合拼接在一起返回，如果不存在则，将新的组合放进字典中。
接下来我们只需要继续遍历list，然后用target减去遍历出来的组合得到差值，然后查看差值是否在hash table中，例如，我们二次以 6 为第一个数去遍历剩下的元素，我们可以得到 [6,4]，得到6 + 4 的结果 10，用16 - 10 = 6， 然后我们查看 字典 中有没有对应的和为6的组合，我们可以发现 [7, -1]是等于6的这时候我们就可以把[7, -1]拿出来和[6, 4]组成一个长度为4的数组[7, -1, 6, 4]，然后加入到结果的数组里面。这样我们就得到了第一个四数之和。请注意：在我们返回结果的时候我们需要去循环整个value数组，因为我们的值是一个二维数组，里面可能又不止一个元素。
请注意第二个需要注意的点！！！
我们的hash table 里面的值有可能出现两次，
举个栗子：
在allPairSums = { 13: [[7, 6]], 3: [[4, -1]], 10: [[6, 4]], 6: [[7, -1]]}中， 我们可以看到，13 + 3 = 16， 10 + 6 =16 字典中的两个4个元素两两组合都是可以得出结果16的，但是他们两两合并之后实际上都是等于[7, 6, 4, -1]，这样我们实际上执行了两计算，同时我们在加入结果的时候也需要做检查，导致了额外的计算。
所以我们该如何避免呢？
举个栗子：
我们在数组 [7, 6, 4, -1, 1, 2] 第一个数选取的是4，我们现在的 字典 是空的{}，我们先向4后面的元素开始遍历，我们可以得到[4, -1]，[4, 1]，[4, 2] ，每当我们得到一个新的组合我们需要去check字典中的值，但是字典现在是空的，所以没有对应的值，但是我们不像之前一样，将字典中没有的值放进去，在4和4后面的值组成的组合我们不放进去 allPairSums 字典中。
然后我们开始遍历4之前的元素，也就是7 ，6，我们可以得到[7, 4] ，去字典中查看是否有对应值，没有就加入字典， 如果有就append到数组和后面。6也是一样，得到[6, 4]，然后去字典中查看，如果没有就加入字典中。现在字典就变成了{ 11: [[7, 4]], 10: [[6,4]]}，如果现在有一个组合是[3,7] 数组就会变成{ 11: [[7, 4]], 10: [[6,4]，[3，7]]}
总结一下上面的思路：第一次被选择数字，和索引在它后面的数字组成的组合不加入 字典中，只有第一次被选择数字，和索引在它前面的数字组合会加入字典中。
这样做的好处：
1. 能够避免加入6，7 和 7，6到数组中，因为只有被选的数字前面的能够加入字典中，这样就是一个单向循环，所以不会出现7，6 的情况，7只能选择和7之前的数字做成组合，但是7之前没有元素，所以它就没有组合。直到6被选择，它前面的数字是7，所以能和7组成 [6, 7] 这个组合。
2. 如果我们在第一次循环的时候就将后面的数字放入进 字典中：如图所示，如果我们在第一次遍历的时候就将元素加入到 字典中，我们就会出现重复组合的问题
接下来我们看代码：
我会放两个版本，一个版本是有注释的，想看没有注释的请将页面拉到最低下。
时间复杂度：
平均时间复杂度是： O(n^2)
时间的复杂度是O(n^2)的原因是，在我们的算法里， array中的每个元素都要被遍历一次，这个时间复杂度是O(n)。在遍历每个元素的时候我们还需要遍历元素前面和后面的元素，这个时间复杂度也是O(n)，剩下的append到结果数组的操作，和计算组合结果的时间操作都是常数时间，也就是O(1)时间。所以总共是O(n^2)
空间复杂度是：O(n^2)
我们需要将每个元素和另一个元素的组合加入进字典O(n)，同时需要将结果append到结果数组中O(n)，所以加起来是O(n^2)
时间复杂度最差的情况是 O(n^3)
大家可以看下图
下面是没有注释的版本
Reference：代码来自Algoexpert，以学习作为主要目的来分享的。
