四数之和

发表于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，18. 4 Sum

先看题目描述

大意就是给定一个整数数组 nums 和一个目标数 target，让我们返回 nums 数组中相加等于 target 的所有四元组，返回的 list 中不能出现重复元素

算法和思路

四数之和与之前做的三数之和的思路基本是一致的，其实就是在三数之和的基础上加了个遍历的指针

使用四个指针，i < j < left < right，i 和 j 指针用于 nums 数组的两层循环，每次循环时，固定最小的 i 和 j 指针在左边，left = i + 1，right = len - 1，移动 left 和 right 指针包夹求解，计算 sum = nums[i] + nums[j] + nums[left] + nums[right]，当 sum = target 时，保存这个解，并同时移动 left 和 right 指针；当 sum < target 时，说明偏小，left右移；当 sum > target 时，说明偏大，right 左移。当 left 和 right 相遇时，则代表以当前 i 和 j 为最小值的的解已经全部求得，则进入下一轮循环

注意：因为要使用双指针的 方法，必须先做个排序

重复解的处理：重复解的出现是因为有重复数字的情况，所以每次移动指针时需要确保指针对应的数字发生了改变

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i <= len - 4; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 确保 nums[i]改变了
            int num1 = nums[i];
            for (int j = i + 1; j <= len - 3; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 确保 nums[j]改变了
                int num2 = nums[j];
                int left = j + 1;
                int right = len - 1;
                if (num1 + num2 + nums[left] + nums[left + 1] > target) break;
                if (num1 + num2 + nums[right] + nums[right - 1] < target) continue;
                while (left < right) {
                    int sum = num1 + num2 + nums[left] + nums[right];
                    if (sum < target) {
                        while (left < right && nums[left] == nums[++left]); // 确保 nums[left]改变了
                    } else if (sum > target) {
                        while (left < right && nums[right] == nums[--right]); // 确保 nums[right] 改变了
                    } else {
                        res.add(Arrays.asList(num1, num2, nums[left], nums[right]));
                        while (left < right && nums[left] == nums[++left]); // 确保 nums[left]改变了
                        while (left < right && nums[right] == nums[--right]); // 确保 nums[right] 改变了
                    }
                }
            }
        }
        return res;
    }
}

注意这两个语句

1
2
if (num1 + num2 + nums[left] + nums[left + 1] > target) break;
if (num1 + num2 + nums[right] + nums[right - 1] < target) continue;

原本提交的代码是没有这两个语句的，运行效率一般，看了击败效率排在前列的代码后，将这两条语句添加了上去，运行效率改善了很多。第一个语句代表以当前 i 和 j 为最小值的四元组的最小和都大于 target，那么就跳出内层循环，移动 i 指针进行下一轮的外层循环；第二个语句代表以当前 i 和 j 为最小值的四元组的最大和都大于 target，那么就直接移动 j 指针进行下一轮的内层循环