M 18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

 

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
 

Constraints:

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

好的，这道题目可以逐字翻译如下：

给定一个整数数组 nums 和一个整数 target，找出 nums 中所有唯一的四元组 [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
你可以以任意顺序返回答案。

示例 1：

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

示例 2：

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

约束条件：

1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

这道题目要求我们在给定的整数数组中找出所有的四元组，这四个数字的和等于目标值。每个四元组中的四个索引需要是唯一的。我们可以以任意顺序返回这些四元组。


best answer
这道题目是四数之和问题，要求我们在一个数组中找到所有的四元组，它们的和等于一个给定的目标值。解决这个问题的一个有效策略是使用双指针法。在这个算法中，我们先对数组进行排序，然后遍历数组中的每个元素，对于每个元素，我们都在它之后的数组中使用双指针法找到和等于目标值减去当前元素的所有对。下面是代码的详细解释：

import java.util.AbstractList;  // 导入AbstractList类，这是一个抽象类，可以实现一些基础的List操作。

class Solution {  // 定义Solution类
    private List<List<Integer>> list;  // 定义一个二维列表，用来存储结果

    public List<List<Integer>> fourSum(int[] nums, int target) {  // 定义函数，输入是一个整数数组和一个目标值，输出是一个二维列表
        return new AbstractList<List<Integer>>(){  // 创建一个AbstractList对象
            public List<Integer> get(int index) {  // 重写get方法，用于获取指定位置的元素
                init();  // 调用init方法，确保结果已经被计算出来
                return list.get(index);  // 返回指定位置的元素
            }
            public int size() {  // 重写size方法，返回列表的大小
                init();  // 调用init方法，确保结果已经被计算出来
                return list.size();  // 返回列表的大小
            }
            private void init() {  // 定义init方法，用于计算结果
                if (list != null)  // 如果结果已经被计算出来，就直接返回
                    return;
                list = new ArrayList<List<Integer>>();  // 创建一个新的列表，用于存储结果
                Arrays.sort(nums);  // 对输入的数组进行排序

                if(nums[0] > 0 && target < 0){  // 如果数组的第一个元素大于0，并且目标值小于0，由于数组已经排序，所以不可能找到和等于目标值的四元组，直接返回
                    return;
                }
                for(int i = 0, L = nums.length; i < L-3; i++) {  // 遍历数组，由于需要找到四个元素，所以只需要遍历到倒数第四个元素

                    for(int j = L-1; j > i+2; j--) {  // 对于每个元素，遍历它后面的所有元素

                        int rem = target-nums[i]-nums[j];  // 计算目标值减去当前两个元素的值，得到剩余的值
                        int lo = i+1, hi=j-1;  // 定义两个指针，分别指向当前元素之后的第一个元素和最后一个元素
                        while(lo < hi) {  // 当左指针小于右指针时，执行以下操作
                            int sum = nums[lo] + nums[hi];  // 计算左指针和右指针指向的元素的和
                            if(sum > rem)  // 如果和大于剩余的值，就将右指针向左移动
                                --hi;
                            else if(sum < rem)  // 如果和小于剩余的值，就将左指针向右移动
                                ++lo;
                            else {  // 如果和等于剩余的值，说明找到了一个有效的四元组
                                long sumCheckOverflow = (long)nums[i] + (long)nums[lo] + (long)nums[hi] + (long)nums[j];  // 计算四元组的和，考虑到可能会有整数溢出的问题，所以使用long类型
                                if(sumCheckOverflow > Integer.MAX_VALUE || sumCheckOverflow < Integer.MIN_VALUE)  // 如果和溢出，就直接返回
                                    return;

                                list.add(Arrays.asList(nums[i],nums[lo],nums[hi],nums[j]));  // 将找到的四元组添加到结果中
                                while(++lo <= hi && nums[lo-1] == nums[lo])  // 如果左指针指向的元素和上一个元素相等，就将左指针向右移动，以避免重复的四元组
                                    continue;
                                while(--hi >= lo && nums[hi] == nums[hi+1])  // 如果右指针指向的元素和下一个元素相等，就将右指针向左移动，以避免重复的四元组
                                    continue;
                            }
                        }
                        while(j >= 1 && nums[j] == nums[j-1])  // 如果当前元素和上一个元素相等，就将当前元素向左移动，以避免重复的四元组
                            --j;
                    }
                    while(i < L-1 && nums[i] == nums[i+1])  // 如果当前元素和下一个元素相等，就将当前元素向右移动，以避免重复的四元组
                        ++i;
                }
                return;  // 返回结果
            }
        };
    }
}

这个算法的时间复杂度是O(n^3)，空间复杂度是O(n)，其中n是输入数组的大小。它首先对数组进行排序，然后通过三层循环找到所有的四元组。为了避免重复的四元组，每次找到一个四元组后，都会移动指针跳过相同的元素。