Leetcode 454. 4Sum II

https://leetcode.jp/leetcode-454-4sum-ii-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/
摘要:
个人认为本题与Two Sum属于同类型题目，主要考察HashMap，而3Sum与4Sum又是另外一个类型，均可使用双指针思路来解题。

分析本题之前，我觉得有必要说下本题与前一集4Sum的区别，虽然都是求4个数和为某个Target的题目，但是区别在于，本题是在4个数组中分别找4个数字，前一题则是在一个数组中找。我们要明白他们在本质上的不同，才能理解为什么不能使用同一种解题方法。当在一个数组中找4个数字时，我们解法使用的时间复杂度为O(n^3)，前两层循环是在找前两个数，第三层循环使用双指针来找后两个数。其实本题也能使用该方法，但是难点在于无法剪枝！4Sum虽然使用了O(n^3)的时间复杂度，但是剪枝操作让其执行次数远远小于n的三次方，剪枝的核心在于，因为只有一个数组，当它排序之后，如果当前数已经大于Target，那么在它后面的其他数字肯定也都大于Target，此时可以结束循环。而回到本题，我们需要在4个数组中分别挑一个数出来，这样，即使当前数字大于Target，我们也不能确定其他数组中挑出的数字是否也都大于Target，这样一来，就没有办法进行剪枝操作了。

那么本题该如何解呢？上文已经说过，本题其实与Two Sum很相似，我们将4个数组分成2组，A，B和C，D，先使用两层循环遍历A和B中所有元素两两之和，并将结果保存至HashMap，其中key为两元素之和，value为该和出现的次数。之后再使用两层循环遍历C和D中所有元素两两之和，并查看该和的相反数在map中存在的个数，并将个数累加至返回结果即可。