描述

给一个包含 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;     } } 

更多题解参考

大佬有話說 (0)