2022-4-30双指针

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

 1 import java.util.*;
 2 class Solution {
 3     public List> fourSum(int[] nums, int target) {
 4         Arrays.sort(nums);
 5         return Sum(nums,4,0,target);
 6     }
 7 
 8 
 9     public List> Sum(int[] nums,int number,int start,int target) {
10         List> list=new ArrayList<>();
11         if (number<2||number>nums.length) return list;
12         if (number==2){
13             int l=start,r=nums.length-1;
14             while (l<r){
15                 int sum=nums[l]+nums[r];
16                 int left=nums[l],right=nums[r];
17                 if (sum<target){
18                     while (l;
19                 }else if (sum>target){
20                     while (l;
21                 }else{
22                     list.add(new ArrayList<>(List.of(left,right)));
23                     while (l;
24                     while (l;
25                 }
26             }
27         }else {
28             
29             for (int index=start;index){
30                 List> arr=Sum(nums,number-1,index+1,target-nums[index]);
31                 for (List temp:arr){
32                     temp.add(nums[index]);
33                     //ArrayList t=new ArrayList<>(temp);
34                     //t.add(nums[index]);
35                     list.add(temp);
36                 }
37                 while (index;
38             }
39         }
40         
41         return list;
42     }
43 }

思路：递归求n-1 Sum问题。注意添加答案时需要时ArrayList 否则无法添加元素，具体见22行。