T18. 4Sum【Medium】
題目
給一個有 n 個整數(shù)的數(shù)組 S岩饼，找到 S 中的所有和為 target 的四元組（S 中元素 a,b,c,d 使得 a+b+c+d = target ）晓勇。找到所有數(shù)組中所有符合要求的四元組缀皱。
注釋： 解答中不能有重復(fù)的四元組
例如, 給出數(shù)組 S = [1, 0, -1, 0, -2, 2],以及 target = 0.
一個解集是:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路
① 思路和前面的題很像荧止，在補充里我會放出鏈接
② 主要要注意的是搜索方式以及去重
③ 下面代碼的搜索方式是前兩個數(shù)用兩個嵌套的 for 循環(huán)依次匹配塘雳，后兩個數(shù)是在第二個數(shù)后面的數(shù)段中從頭和尾分別向中間靠攏氏捞，由于排好序了惩妇，所以偏大時株汉，第三個數(shù)往右選，偏小時第四個數(shù)往左選
④ 去重的話通過 while 循環(huán)在四個數(shù)用到的時候分別判斷并且去重歌殃，可以看代碼乔妈，我有標(biāo)注
代碼
代碼取自 Top Solution，稍作注釋
public List<List<Integer>> fourSum(int[] num, int target) {
ArrayList<List<Integer>> ans = new ArrayList<>();
//當(dāng)小于4時不存在氓皱，所以直接返回
if(num.length<4)return ans;
//排序
Arrays.sort(num);
for(int i=0; i<num.length-3; i++){
//去掉重復(fù)的數(shù)字
if(i>0&&num[i]==num[i-1])continue;
for(int j=i+1; j<num.length-2; j++){
//去掉重復(fù)的數(shù)字
if(j>i+1&&num[j]==num[j-1])continue;
//剩下low和high兩個數(shù)字在后面網(wǎng)中間夾
int low=j+1, high=num.length-1;
while(low<high){
int sum=num[i]+num[j]+num[low]+num[high];
if(sum==target){
//相等時加入數(shù)組
ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
//這兩個while也是去重
while(low<high&&num[low]==num[low+1])low++;
while(low<high&&num[high]==num[high-1])high--;
low++;
high--;
}
//由于排好序了路召，所以偏大時，第三個數(shù)往右選波材，偏小時第四個數(shù)往左選
else if(sum<target)low++;
else high--;
}
}
}
return ans;
}
補充
leetcode 的第十五題和第十六題的題目代碼思想和這個很相近股淡，可以看一下~
