LeetCode_52_4sum

发布日期: 2022-05-10

更新日期: 2022-05-10

文章字数: 1.3k

阅读时长: 5 分

阅读次数:

1. question: 四数之和（中等）

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum

示例 1：

1 2	输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

1 2	输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：

1
2
3

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

2. answers

这道题的思路和三数之和是类似的。先对数组排序，采用四指针法来做，两个基础指针，两个首尾指针。注意，由于target是任意的，所以就可能存在负数的情况，那么此时就不能像三数之和那样提前判断是否大于target了，因为负数相加会越来越小。必须保证当前元素大于0才能判断是否大于target，这样才能保证当前元素的后续元素是正数，相加肯定越来越大。代码如下所示：

public class Solution_0050 {

    public static List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();

        if(nums.length < 4) return result;

        Arrays.sort(nums);

        int head, tail, sum;

        for (int i = 0; i < nums.length - 3; i++) {

            // 判断当前元素是否与上一个位置的元素相同，如果相同，则直接进行下个元素遍历，因为这可能出现重复结果
            if(i > 0 && nums[i] == nums[i-1]) continue;

            // 注意，这里不能如下判断，因为存在负数的情况，负数相加会越来越小的
            // 如果当前数已经大于target，那么就没必要进行后面的计算了，因为这是排序后的数组，后面肯定会越来越大。
//            if(nums[i] > target) return result;

            // 为什么三数之和的时候，就可能判断呢？因为三数之和求的是0, 这个0既表示当前元素是正数，也表示后续元素也是正数
            // 所以在判断之前，一定要保证当前元素是正数。
            if(nums[i] > target && nums[i] > 0) return result;

            for (int j = i + 1; j < nums.length - 2; j++) {

                // 判断当前元素是否与上一个位置的元素相同，如果相同，则进行下个元素遍历，因为这可能出现重复结果
                // 注意，此判断指的是第一个基础指针不变的情况下，如果第一个指针已经改变了，那么此处就不需要判断了。
                // 如何判断第一个基础指针是否改变呢，可以判断两个基础指针是否相差一个位置，如果大于一个位置，那么就说明第一个基础指针没变
                // 即当前循环是在改变第二个基础指针
                if(j - i > 1 && nums[j] == nums[j-1]) continue;

                // 注意，这里不能如下判断，因为存在负数的情况，负数相加会越来越小
                // 如果当前两数之和已经大于target，那么就没必要进行后面的计算了，因为这是排序后的数组，后面肯定会越来越大。注意，这里应该是continue
                // 因为两个基础指针如果相差较多，即第一个指针在最开始，第二个指针在最后，这并不能代表第一个位置在index=2，第二个指针在index=3处，不会出现结果
                // 所以此处，应该是continue。和第一个基础指针还是有区别的。
//                if(nums[i] + nums[j] > target) continue;

                // 两层循环表示两个基础指针，下面设置首尾指针
                head = j + 1;
                tail = nums.length - 1;

                while(head < tail) {

                    sum = nums[i] + nums[j] + nums[head] + nums[tail];

                    if(sum > target) {
                        tail --;
                    } else if(sum < target) {
                        head ++;
                    } else {

                        List<Integer> temp = new ArrayList<>();

                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[head]);
                        temp.add(nums[tail]);

                        result.add(temp);

                        head ++;
                        tail --;

                        while(nums[head] == nums[head-1] && head < tail) head ++;

                        while(nums[tail] == nums[tail+1] && tail > head) tail --;
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] nums = {1, 0, -1, 0, -2, 2};
//        int[] nums = {2, 2, 2, 2, 2};
//        int[] nums = {-2,-1,-1,1,1,2,2};
//        int[] nums = {-5, -4, -3, -2, -1, 0, 0, 1, 2, 3, 4, 5};
        int[] nums = {1, -2, -5, -4, -3, 3, 3, 5};

        List<List<Integer>> result = fourSum(nums, -11);

        System.out.println("结果如下所示：");

        for (List<Integer> temp : result ) {

            for (Integer integer : temp) {
                System.out.print(integer + "\t");
            }

            System.out.println();
        }

    }
}