LeetCode | 类似的题目太多，四数之和比三数之和多了一层循环

类似的题目都是由相同的数据去解决的，这说法到底对不对，可能要等多年看看是不是被打脸了。

看下面有些题目的标签是类似的。三数之和可以参考两数之和的解题方法，也可以先排序，固定一个数，进行双指针法，或者两种方式都用上。就看你怎么思考了。

思考完之后选最优的解题方式就好了。

接下来我就跳过一些题目，如果对数据结构不太熟悉的可以连着做，不管是难度还是通过率。

那么我就做18号题，这道题目光想想数据结构就有点头大，但是联想到前面做的两道题目，就大概知道怎么回事了。

这次就不写暴力解法了，四层循环嘛，时间复杂度达到O(n^4)。

哈希表的解法可以参考L1两数之和的题目，此道题目如果用哈希表解法会比较复杂，时间复杂度和空间复杂度都要比双指针大。

双指针相对比较容易，时间复杂度是在O(n^2)，如果三数之和的话那就在O(n)，四数之和比三数之和多了一层循环。

下面就按步骤解释双指针的解法吧，完了之后再用哈希解法，看看会有何不同。

为了能够利用双指针，我们首先把这个例子排一下序，这样可以根据临近值的大小进行判断。

然后先固定两个数，如果是三数之和的话就先固定一个数。如果有能力的话可以尝试一下方法化，参数为几数之和。

然后创建双指针，在一组数字右部分置于两端，到时候可以根据偏大还是偏小，进行左右指针的移动。

同样也做出视频下来，请欣赏！（注意，视频中的“跳过”是程序的判断）

然后贴代码：

看完双指针的解决办法之后，感觉很简单，难的是要进行很多的判断。

如果按哈希表来做呢？会有怎么样的效果？

这道题的做法，数组可以不用排序。因为在整个使用哈希表的过程中，一点没用到关于双指针的做法。

我这里已经做好视频了，视频中套用了前面的视频，安排了数组的排序。没关系，你可以假装它没有排序。

看好了。

有序选择两个数求和，比如选择-2和-1，求和是-3。作为哈希表的结构可以写成{-3:[0,1]}。其中0和1是数字的下标。

如果求和过程中会碰到重复的键，可以写成{-3:[[0,1]]}。这样的[[]]也是一个二维数组。

再比如选择-1和0，求和是-1，那结果是{-1:[[1,2],[1,3],[0,4],]}。

做到这里也有两种方式，两种方式和L1题目有非常大的类似，详见参考L1两数之和，要注意看到最后的小视频。

两种方式的不同只是参照物不同，但计算量差距还是蛮大的。

第一种，看上面图片，如果有序选择两个数-2和-1，求和是-3。target=0的话，target– (-3) = 3，而右边存在一个键3，得到的相应下标是[4,5]。下标为4的数字是1，下标为5的数字是2，那就可以返回[-2,-1,1,2]这个数组了。以此类推，再接着有序选择两个数，继续。。。

贴代码：

第二种的话就比较复杂，忽略掉上面的数组，光去操作右边Map键值对的数字。需要考虑到map.entrySet()转化为Iterator类对象，得到它们的二维数组一个一个判断。可以的话也可以用Compare去重写一下两个二元数组的比较。

贴代码：

第二种方法的部分代码也贴上来：

最后也做出部分视频上来，请欣赏！（文章中间部分也制作出双指针的算法，一眼可以看懂）

——END——