算法面試真題詳解： 四數之和

描述

給一個包含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中的答案輸出

最差情況搜尋為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