LeetCode-18.四数之和

以你之姓@ 2022-01-31 13:47 127阅读 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\] \]

解题思路—**双指针**：**这题是[LeetCode-15.三数之和][LeetCode-15.]的进阶版**，核心思想一模一样，但是因为变成了四个数，同时要注意判断是否含有重复的情况，所以为了**避免加入重复数组，要以第一个和第二个数为基准，剩下两个数作为左右指针遍历**。（为什么选第一个和第二个作为基准，而不是随机两个，**第15题中有详细解答**，看懂**三数之和**，也就能理解这题。其实使用**ArrayList中的contains也能判断**，就是复杂度高一点。）

## Java解题—双指针 ##

import java.util.List;
    import java.util.ArrayList;
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new ArrayList<>();
            int len = nums.length;
            Arrays.sort(nums);
            for(int i=0;i<len-3;i++){
                if(i>0 && nums[i]==nums[i-1]) continue;
                int sum = target - nums[i];
                for(int j=i+1;j<len-2;j++) {
                    if(j>i+1 && nums[j]==nums[j-1]) continue;
                    int su = sum - nums[j];
                    int l = j + 1, r = len - 1;
                    
    //                使用ArrayList中的contains判断
    //                while (l < r) {
    //                    if (nums[l] + nums[r] == su) {
    //                        if (!res.contains(Arrays.asList(nums[i], nums[j], nums[l], nums[r])))
    //                            res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
    //                        l++;
    //                        r--;
    //                    } else if (nums[l] + nums[r] > su)
    //                        r--;
    //                    else
    //                        l++;
    //                }
    
                    while (l < r) {
                        if (nums[l] + nums[r] == su) {
                            res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                            while(l<r && nums[l+1]==nums[l]) l++; l++;
                            while(l<r && nums[r-1]==nums[r]) r--; r--;
                        } else if (nums[l] + nums[r] > su){
                            while(l<r && nums[r-1]==nums[r]) r--; r--;
                        }
                        else{
                            while(l<r && nums[l+1]==nums[l]) l++; l++;
                        }
    
                    }
                }
            }
            return res;
        }
    }

[LeetCode-15.]: https://blog.csdn.net/gaoyueace/article/details/90258322