题目

18. 四数之和

难度中等808 收藏 分享 切换为英文 接收动态 反馈

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + 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 = [], target = 0
输出：[]

提示：

• 0 <= nums.length <= 200
• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
• -10<sup>9</sup> <= target <= 10<sup>9</sup>

思路

这个就没什么特别的了，直接参考三数之和：【LeetCode】15、三数之和为0

网上也没有找到什么其他特别的解法，有说采用二分的方法转化为两个两数之和的，但是感觉过于繁琐了，不太直观，这里就直接采用在三数之和的外层又加了一层循环，时间复杂度为：O(n^3).

然后主要对这类题做一个总结：

两数之和系列，做法：

• 若数组无序，采用HashMap，参考：【LeetCode】1、两数之和
• 若数组有序，双指针，参考：【剑指Offer】42、和为S的两个数字

三数之和（N数之和）序列，做法:

• 第一步：java.util.Arrays.sort(int[] nums)，升序排列
• 第二步：N-2层for循环，外加两个双向指针，双向指针后需while循环向数组中间靠拢，while循环里嵌套两层while循环，用于去重

java代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        if(nums==null && nums.length==0)
            return res;
        Arrays.sort(nums);
        int len=nums.length;
        for(int i=0;i<len-3;i++){
            if(i>0 && nums[i-1]==nums[i]) //跳过重复的
                continue; 
            for(int j=i+1;j<len-2;j++){
                if(j>i+1 && nums[j]==nums[j-1])  //跳过重复的
                    continue;
                int low=j+1,high=len-1,sum=target-nums[i]-nums[j];
                while(low<high){
                    if(nums[low]+nums[high]==sum){ //找到一个解
                        res.add(Arrays.asList(nums[i],nums[j],nums[low],nums[high]));
                        while(low<high && nums[low+1]==nums[low])
                            low++;
                        while(low<high && nums[high-1]==nums[high])
                            high--;
                        low++;
                        high--;
                    }else if(nums[low]+nums[high]<sum)
                        low++;
                    else
                        high--;
                }
            }
        }
        return res;
    }
}