算法面试真题详解：四数之和

2023-11-28 20:58:52

描述
给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
四元组(a, b, c, d)中，需要满足a <= b <= c <= d
答案中不可以包含重复的四元组。

样例 1:
输入:[2,7,11,15],3
输出:[]

样例2：
输入:[1,0,-1,0,-2,2],0
输出:
[[-1, 0, 0, 1]
,[-2, -1, 1, 2]
,[-2, 0, 0, 2]]

算法：DFS / 双指针

DFS：
朴素DFS，对排序后的队列进行搜索每次选取当前数后的比当前值大的数压入List，当List大小为4的时候判断是否四个元素的和为taeget
对数组排序
用List记录选取的元素
由于已经升序排列，只需要要去找上个元素的后面的位置的元素作为下一个元素
若List大小为4，且和为target的时候记录一次答案

复杂度分析

时间复杂度O(n^3)
最差情况搜索为n^3
空间复杂度O(n*n)
存储答案的大小
双指针：
虽然题目是四数之和，但是我们可以将他转换为三数之和，再进一步就是二数之和，先进行稳定排序，然后我们准备用四个指针
先用将问题看待为三数之和，即一个指针和三个指针
再将这三个指针看成二数之和，即一个指针和两个指针
那么问题就被化简了，先框定两个指针，再在这个基础上，用双指针解决问题，当头指针和尾指针的元素之和大于new_target,尾指针-1(因为头指针+1的结果肯定大于new_target),同理当头指针和尾指针的元素之和小于new_target,头指针+1。
对序列排序，用一个set存储答案，因为有可能存在相同的答案
用两个for循环嵌套，代表第一二个指针
然后用一对双指针从第二个指针后面的位置向右和末尾向左进行移动
如果四个指针的和等于target,将这组答案添加，如果小于的话左指针右移，反之右指针左移
将set中的答案输出

复杂度分析

时间复杂度O(n^3)
最差情况搜索为n3n3
空间复杂度 O(n^2)
存储答案的大小
//DFS

public class Solution {
    /**
     * @param numbers: Give an array
     * @param target: An integer
     * @return: Find all unique quadruplets in the array which gives the sum of zero
     */
    public List<List<Integer>> fourSum(int[] numbers, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        //排序
        Arrays.sort(numbers);
        //DFS
        dfs(numbers, new ArrayList<Integer>(), target, ans, 0);
        return ans;
    }

    private void dfs(int[] numbers, List<Integer> list, int target, List<List<Integer>> ans, int index) {
        //判断值是否符合要求
        if (list.size() == 4) {
            if (target == 0) {
                ans.add(new ArrayList<Integer>(list));
            }
            return;
        }
        for (int i = index; i < numbers.length; i++) {
            if (i != index && numbers[i] == numbers[i-1]) {
                continue;
            }
            //选取当前元素
            list.add(numbers[i]);
            dfs(numbers, list, target-numbers[i], ans, i+1);
            list.remove(list.size() - 1);
        }
    }
}
//双指针
public class Solution {
    /**
     * @param numbers: Give an array
     * @param target: An integer
     * @return: Find all unique quadruplets in the array which gives the sum of zero
     */
    public List<List<Integer>> fourSum(int[] numbers, int target) {
        Set<List<Integer>> res = new HashSet<List<Integer>>();//用set可以避免出现重复答案
        Arrays.sort(numbers);
        int size = numbers.length;
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        for (int i = 0; i < size - 3; i++) {//第一个指针
            for (int j = i + 1;j < size - 2;j++) {//第二个指针
                if (j > i + 1 && numbers[j] == numbers[j-1]) {
                    continue;
                }
                int left = j + 1,right = size - 1;//第三第四个指针
                while (left < right) {
                    int sum = numbers[i] + numbers[j] + numbers[left] + numbers[right];
                    if (sum == target) {//如果序列和=target，将序列添加到set中
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(numbers[i]);
                        tmp.add(numbers[j]);
                        tmp.add(numbers[left]);
                        tmp.add(numbers[right]);
                        res.add(tmp);
                        left++; //左指针向右
                        right--;//右指针向左
                    }
                    else if (sum < target) {//如果序列和比target小，左指针向右
                        left++;   
                    }     
                    else {//如果序列和比target大，右指针向左
                        right--;
                    } 
                }
            }
        }
        for (List<Integer> tmp:res) {//输出结果
            ans.add(tmp);
        }
        return ans;
    }
}

更多题解参考：九章官网solution

码农公寓

算法：DFS / 双指针

复杂度分析

复杂度分析

相关文章