一文 学透 力扣—N数之和

题目一：1. 两数之和❤

题目思路

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key — value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

下方图解：

                             

题解代码

/*使用hashMap存放nums中已经遍历过的值【做个记录】在后序遍历中，判断是否存在已经遍历过的值和正在遍历的值之和恰好等于target*/
public int[] twoSum(int[] nums, int target) {// 定义一个map集合存放nums数组中的元素及其索引 {key：数据元素，value：数组元素对应的下标}Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int prevNum = target - nums[i]; //如果数组中之前出现过prevNum，则说明两数和可以等于targetif (map.containsKey(prevNum)) {// 如果之前存在过，则返回索引return new int[]{map.get(prevNum), i};} else {// 否则将当前的值和索引作为map的键和值加入到map中map.put(nums[i], i);}}return null;
}

题目二：167. 两数之和 II - 输入有序数组

题目思路

题目的前提是：数组中的元素初始状态就是有序的

• 两个指针i和j分别指向最左侧和最右侧的数字

• 它俩指向的数字和与target相比

  • 小于target i++向右找

  • 大于target j--向左找

  • 等于target找到

题解代码

/*思路- 两个指针i和j分别指向最左侧和最右侧的数字- 它俩指向的数字和与target相比- 小于target i++向右找- 大于target j--向左找- 等于target找到*/
public int[] twoSum(int[] numbers, int target) {int i = 0;int j = numbers.length - 1;while (i < j) {int sum = numbers[i] + numbers[j];if (sum > target) { // 大于target j--向左找j--;} else if (sum < target) { // 小于target i++向右找i++; } else { // 等于target找到break;}}return new int[]{i + 1, j + 1};
}

题目三：15. 三数之和❤❤️❤️

题目思路

视频讲解：https://www.bilibili.com/video/BV1rv4y1H7o6/?p=178

双指针

这道题目使用双指针法 要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

拿这个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相遇为止。

去重逻辑的思考

a的去重

说到去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。

如果我们的写法是 这样：

if (nums[i] == nums[i + 1]) { // 去重操作continue;
}

那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) {continue;
}

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

这是一个非常细节的思考过程。

b与c的去重

很多同学写本题的时候，去重的逻辑多加了 对right 和left 的去重：（代码中注释部分）

while (right > left) {if (nums[i] + nums[left] + nums[right] > 0) {right--;// 去重 rightwhile (left < right && nums[right] == nums[right + 1]) right--;} else if (nums[i] + nums[left] + nums[right] < 0) {left++;// 去重 leftwhile (left < right && nums[left] == nums[left - 1]) left++;} else {}
}

但细想一下，这种去重其实对提升程序运行效率是没有帮助的。

拿right去重为例，即使不加这个去重逻辑，依然根据 while (right > left) 和 if (nums[i] + nums[left] + nums[right] > 0) 去完成right-- 的操作。

多加了 while (left < right && nums[right] == nums[right + 1]) right--; 这一行代码，其实就是把 需要执行的逻辑提前执行了，但并没有减少 判断的逻辑。

最直白的思考过程，就是right还是一个数一个数的减下去的，所以在哪里减的都是一样的。

所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已

而真正去重b和c的代码应该放在找到一个三元组之后，对b 和 c去重，并且去重后需要对left和right同时收缩

题解代码

代码一：迭代型

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();// 先排序Arrays.sort(nums);// 排序后数组的第一个值如果大于0，则三数之和后一定不可能有等于0的情况，直接返回if (nums[0] > 0) {return res;}/*使用i指针固定一个值a,使用left指针固定一个值b，使用right指针固定一个值c指针 i 的取值范围 [0,nums.length-3],因为后面最少还需要留两个位置给right和left*/for (int i = 0; i < nums.length-2; i++) {// 对a进行去重if (i > 0 && nums[i] == nums[i - 1]) {continue;}int right = nums.length - 1;int left = i + 1;while (left < right) {// 三数之和int sum = nums[i] + nums[left] + nums[right];// 如果三数之和大于0，则需要将right--，反之将left++if (sum > 0) {right--;} else if (sum < 0) {left++;} else { // 找到第一个三数和为0，加入结果集合后对数字b和c进行去重res.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;// 找到答案时，双指针同时收缩left++;right--;}}}return res;
}

 代码二：递归型

List<List<Integer>> result = new LinkedList<>();
LinkedList<Integer> stack = new LinkedList<>();List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 先排序，方便去重dfs(3, 0, nums.length - 1, 0, nums);return result;
}/**** @param nSum 几数之和* @param i 右指针* @param j 左指针* @param target 目标值* @param nums 原数组*/void dfs(int nSum, int i, int j, int target, int[] nums) {if (nSum == 2) {// 套用两数之和求解twoSum(i, j, nums, target);return;}for (int k = i; k < j; k++) { // 循环固定第一个数// 检查重复，如果出现重复，则跳过if (k > i && nums[k] == nums[k - 1]) {continue;}// 固定一个数字，再尝试 nSum-1 数字之和stack.push(nums[k]);dfs(nSum - 1, k + 1, j, target - nums[k], nums);stack.pop();}
}public void twoSum(int i, int j, int[] numbers, int target) {while (i < j) {int sum = numbers[i] + numbers[j];if (sum < target) {i++;} else if (sum > target) {j--;} else { // 找到解ArrayList<Integer> list = new ArrayList<>(stack);list.add(numbers[i]);list.add(numbers[j]);result.add(list);// 继续查找其它的解i++;j--;// 去重while (i < j && numbers[i] == numbers[i - 1]) {i++;}while (i < j && numbers[j] == numbers[j + 1]) {j--;}}}
}

---

题目四：18. 四数之和

题目思路

核心思路和三数之和类似，只是需要多套一层循环（表示第二个指针），大体思路仍然是先对数组进行排序，然后固定第一个指针，移动第二个指针，第三个指针（left）和第四个指针（right）分别指向第二个指针右侧和数组最后一位，然后在判断四数之和和target的大小，如果四数之和大于target，想让四数之和变小，则需要将right--，如果四数之和小于target，想让其变大，则将left++，如果第三个指针和第四个指针相遇，则移动第二个指针，继续判断...

需要注意的点：

1. 不能向三数之和那样判断第一个值大于0，则直接返回，因为四数之和这道题目的四个数之和不是要求为0，而是要求等于参数target

2. 第一个指针的范围就是在 [ 0 ~ len -4 ] 范围，不能超过len - 4，因为如果第一个指针就超过len - 4，那么后面的 2,3,4 指针则没有位置。

3. 第二个指针的范围就是[ 1 ~ len - 3 ]，原因同上。

4. 对于剪枝的代码，如果四个连续的数相加大于target，因为数组有序，后序也不会再出现四数和等于target的情况了，直接跳出循环（break），如果当前第一个指针的值加上数组中后面三个最大的值任然小于target，则跳出当前循环（continue），因为即使加上数组中最大的三个数仍然小于target，说明第一个指针就是小的，需要跳过，使指针向右继续移动，达到剪枝的目的

5. 力扣的题解有大数，四数之和的上限超过了int类型的上限，因此在这里计算四数之和需要开long型

题解代码

public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int len = nums.length;// 第一个指针i，用于指向a数，范围[0 ~ len-4]for (int i = 0; i < len - 3; i++) {// 剪枝，如果四个连续的数相加大于target，因为数组有序，后序也不会再出现四数和等于0的情况了，直接跳出循环if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}// 剪枝，如果当前第一个指针的值加上数组中后面三个最大的值任然小于target，则跳出当前循环，使指针向右继续移动if ((long) nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {continue;}// 对a进行去重if (i > 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < len - 2; j++) { // 三数之和// 剪枝，同上if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}// 剪枝，同上if ((long)nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {continue;}// 对b数进行去重if (j > i + 1 && nums[j] == nums[j - 1]) continue;int left = j + 1;int right = len - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum > target) { right--; // sum大于target，使right--} else if (sum < target) {left++; // sum小于target，使left++} else {// 找到四个数之和等于target，加入结果集合res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 对c数和d数进行去重while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;// 去重后还需要缩小指针范围left++;right--;}}}}return res;
}