LeetCode——四数之和

Dear 丶 2022-12-13 13:00 163阅读 0赞

## 题目 ##

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = \[1, 0, -1, 0, -2, 2\]，和 target = 0。

满足要求的四元组集合为：

[
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

## 题解 ##

从题目中可以获取以下几条信息：

1.  数组元素为int类型，无序，数组元素可重复
2.  找到所有满足条件且不重复的四元组，意思是说结果可能为多个。不重复要求结果要去重，比如\[-1, 0, 1, 0\]与\[0, 1, -1, 0\]其实是一个结果。

## 解题思路 ##

该题的解题思路类似于[《三数之和》][Link 1]，只不过比三数之和多了一层循环而已。

### 方法一：爆力搜索法 ###

使用四层循环来枚举四元组，这样我们就能得到满足要求的所有四元组，时间复杂度为O(n^4)，之后我们还需要使用哈希表对结果进行去重操作以便得到不重复的四元组，会消耗大量的空间。因此该方法时间复杂度和空间复杂度将会很高。

### 方法二：排序+双指针法 ###

思路可参考[《三数之和》][Link 1]

具体实现时，还可以进行一些剪枝操作：

*  在确定第一个数之后，如果nums\[i\]+nums\[i+1\]+nums\[i+2\]+nums\[i+3\] > target，说明此时剩下的三个数无论怎么取都有四数之和一定大于target，因此可以直接退出循环；
 *  在确定第一个数之后，如果nums\[i\]+nums\[n-1\]+nums\[n-2\]+nums\[n-3\] < target，说明此时剩下的三个数无论怎么取都有四数之和一定小于target，因此第一层循环可以直接进行下一轮枚举；
 *  在确定两个数之后，如果nums\[i\]+nums\[j\]+nums\[j+1\]+nums\[j+2\] > target，说明此时剩下的两个数无论怎么取都有四数之和一定大于target，因此可以直接退出循环；
 *  在确定两个数之后，如果nums\[i\]+nums\[j\]+nums\[n-1\]+nums\[n-2\] < target，说明此时剩下的两个数无论怎么取都有四数之和一定小于target，因此第二层循环可以直接进行下一轮枚举；

### 具体代码实现 ###

class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> results = new ArrayList<List<Integer>>();
            // 首先判断数组长度
            if (nums.length < 4) {
                return results;
            }
            Arrays.sort(nums);
    
            int length = nums.length;
    
            // 第一层枚举 a
            for (int first=0; first<length-3; ++first) {
                // 保证和上次枚举的元素值不同
                if (first>0 && nums[first]==nums[first-1]) {
                    continue;
                }
                // 确定了元素a之后，由于数组从小到大排序，如果数组前四个元素之和大于target，则一定不存在a+b+c+d=target
                if (nums[first]+nums[first+1]+nums[first+2]+nums[first+3]>target) {
                    break;
                }
                // 确定了元素a之后，由于数组从小到大排序，如果数组最后三个元素之和小于target-a，则一定不存在a+b+c+d=target
                if (nums[first]+nums[length-1]+nums[length-2]+nums[length-3] < target){
                    continue;
                }
                // 第二层枚举 b
                for (int second=first+1; second<length-2; ++second) {
                    // 保证和上次枚举的元素值不同
                    if (second>first+1 && nums[second]==nums[second-1]){
                        continue;
                    }
                    // 确定了元素a、b之后，由于数组从小到大排序，如果数组前四个元素之和大于target，则一定不存在a+b+c+d=target
                    if (nums[first]+nums[second]+nums[second+1]+nums[second+2] > target) {
                        break;
                    }
                    // 确定了元素a、b之后，由于数组从小到大排序，如果数组最后两个元素之和小于target-a-b，则一定不存在a+b+c+d=target
                    if (nums[first]+nums[second]+nums[length-1]+nums[length-2] < target) {
                        continue;
                    }
    
                    // 双指针遍历
                    int third = second+1;   // 左指针
                    int four = length-1;    // 右指针
                    int sum = target - nums[first] - nums[second];
                    while (third < four) {
                        while (third<four && nums[third] + nums[four] > sum) {
                            --four;
                        }
                        while (third<four && nums[third] + nums[four] < sum) {
                            ++third;
                        }
                        if (third < four && nums[third] + nums[four]==sum) {
                            List<Integer> result = new ArrayList<Integer>();
                            result.add(nums[first]);
                            result.add(nums[second]);
                            result.add(nums[third]);
                            result.add(nums[four]);
                            results.add(result);
                            ++third;
                            --four;
                            // 保证和上次枚举c的元素值不同
                            while (third<four && nums[third]==nums[third-1]){
                                ++third;
                            }
                            // 保证和上次枚举d的元素值不同
                            while (third<four && four!=nums.length-1 && nums[four]==nums[four+1]){
                                --four;
                            }
                        }
    
                    }
                }
            }
            return results;
        }
    }

## 复杂度分析 ##

*  时间复杂度：O(n^3)，其中n为数组nums的长度
 *  空间复杂度：O(logn)，忽略存储答案的空间，排序的空间复杂度为O(logn)。这种情况下我们修改了输入的数组nums，实际情况可能不一定允许，因此也可以看成使用了一个额外的数据存储了nums的副本进行排序，空间复杂度为O(n)

[Link 1]: https://blog.csdn.net/YF_Li123/article/details/108979730