两数之和，想必刷过leetcode都知道，作为第一道题目，是我们算法刷题的开门砖。随后逐步进阶为三数之和，四数之和。从最开始的哈希，到最后的双指针解法，我们可以学到很多。
文章目录
1. 两数之和
1.1 题目描述
题目链接：1. 两数之和
1.2 思路分析
本题使用HashMap来存储target-nums[i] 与 i 的值，然后在遍历过程中，如果发现key已经存在，则输出对应的value。
Java代码实现：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
// 存储元素值与下标
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
res[0] = i;
res[1] = map.get(nums[i]);
return res;
}
map.put(target - nums[i], i);
}
return res;
}
}
2. 两数之和进阶四数相加Ⅱ
2.1 题目描述
题目链接：454. 四数相加 II
2.2 思路分析
这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。
我们可以将四个数组分成两部分，A 和 B 为一组，C 和 D 为另外一组。
对于 A 和 B，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]，对应的值为 A[i]+B[j] 出现的次数。
对于 C 和 D，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l] 时，如果 ?(C[k]+D[l]) 出现在哈希映射中，那么将 ?(C[k]+D[l]) 对应的值累加进答案中。
最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0 的四元组数目。
Java代码实现：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
// 分成两部分，A和B存哈希表，C和D从哈希表里找
HashMap<Integer, Integer> map = new HashMap<>();
for (int num1 : nums1) {
for (int num2 : nums2) {
map.put(num1 + num2, map.getOrDefault(num1 + num2, 0) + 1);
}
}
int res = 0;
for (int num3 : nums3) {
for (int num4 : nums4) {
if (map.containsKey(-num3-num4)) {
res += map.get(-num3-num4);
}
}
}
return res;
}
}
3. 两数之和高级三数之和
3.1 题目描述
题目链接：15. 三数之和
3.2 思路分析
这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
而且使用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。
这道题目使用双指针法 要比哈希法高效一些。
拿nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]， b = nums[left]， c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
在实现过程中有一些需要剪枝操作，因为去重，所以要对数组排序。
首先排序后，如果nums[i]大于0，则和不会等于0.
if (nums[i] > 0) break;
然后，对nums[i] 去重剪枝
if (i > 0 && nums[i] == nums[i - 1]) continue;
最后，对于同一个的nums[i]，对于相同的nums[left]和nums[right]进行剪枝
// 如[-2, -1, -1, -1, 3, 3, 3]
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
Java代码实现：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 这道题需要去重，所以哈希表不好用，因此采用双指针来实现
// for循环一次，一个指针为i,一个指针为left,一个指针为right,
// 则 a,b,c为nums[i],nums[left],nums[right]
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
if (n < 3) return res;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
// 排过序，如果第一个元素大于0，直接break
if (nums[i] > 0) break;
// 剪枝，用过的元素不能再用，所以需要先排序
if (i > 0 && nums[i] == nums[i - 1]) continue;
int target = -nums[i];
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
// 直接将三个元素组成数组转成list
res.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 先移动再判断
left++;
right--;
// 对于相同的nums[i]，去掉重复的nums[left]和nums[right]
// 如[-2, -1, -1, -1, 3, 3, 3]
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[left] + nums[right] < target) { // 三数之和小了，left 就向右移动
left++;
} else { // 此时三数之和大了，所以right下标就应该向左移动
right--;
}
}
}
return res;
}
}
4. 两数之和终极四数之和
4.1 题目描述
题目链接：18. 四数之和
4.2 思路分析
四数之和，和15.三数之和 是一个思路，都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。
但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。
15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[i] + nums[j]为确定值，依然是循环内有left和right下表作为双指针，找出nums[i] + nums[j] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^ 2)，四数之和的时间复杂度是O(n^3) 。
在实现过程中有一些需要剪枝操作，因为去重，所以要对数组排序。
首先第一重for循环，对于nums[i]，如果重复则去重：
if(i > 0 && nums[i] == nums[i - 1]) continue;
如果前四个数的和超过target，则直接退出
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
如果第一个数与最后三个数的和小于target，则continue:
if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
第二重for循环，是对第二个数的确定，与第一个去重条件类似：
首先元素不能重复使用：
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
在确定了i 和 j ，前四个数的和超过target，则直接退出
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
在确定了i 和 j ，与最后两个数的和小于target，则：
if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
Java代码实现：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
if (n < 4) return res;
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
if(i > 0 && nums[i] == nums[i - 1]) continue; //去重, 用过一次的数字不能用第二次
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
// 和超过则直接退出循环
break;
}
if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
// 三数之和时，只要确定一个i,就可以使用双指针找target-nums[i]
// 四数之和时，需要确定两个数，故多加一层循环j,然后双指针找另外两个数
for (int j = i + 1; j < n - 2; j++) {
// 和上一层循环一样的判断条件
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
// 双指针
int left = j + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 去掉重复的后，加加减减
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
总之，从最开始的两数之和，使用哈希法可以计算对应的数的位置，然后四数相加的时候，把数据分成两部分，用哈希法去计算。到最后的三数之和和四数之和时，使用哈希法就不好处理去重问题和超时的问题，因此采用双指针法，并进行优化。