每日一道 LeetCode (56)：四數(shù)之和
每日一道 LeetCode (56)：四數(shù)之和
每天 3 分鐘，走上算法的逆襲之路。
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：四數(shù)之和
難度：中等
題目來(lái)源：https://leetcode-cn.com/problems/4sum/
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。
注意：
答案中不可以包含重復(fù)的四元組。
示例：
給定數(shù)組 nums =?[1, 0, -1, 0, -2, 2]，和 target =?0。
滿足要求的四元組集合為：
[
??[-1,??0,?0,?1],
??[-2,?-1,?1,?2],
??[-2,??0,?0,?2]
]
解題思路
這道題有點(diǎn)方，雖然前面曾經(jīng)做過(guò)一個(gè)三數(shù)之和的題，但是看到這個(gè)題完全沒(méi)和前面的那道題產(chǎn)生聯(lián)系。
最蠢的方案就是套 4 層循環(huán)，暴力循環(huán) 4 次，雖然我沒(méi)這么干，但是這么干肯定超時(shí)，我在題解的評(píng)論里面見(jiàn)到有人真的用了 4 層循環(huán)，真的猛士，這道題 4 層循環(huán)想要寫通并不是那么簡(jiǎn)單的。
除了 4 層循環(huán)，那么 3 層循環(huán)行不行，當(dāng)然可以，答案上給出來(lái)的就是三重循環(huán)。
套路還是和之前的三數(shù)之和一樣，使用雙指針，使用兩層循環(huán)分別枚舉前兩個(gè)數(shù)，之后使用雙指針在同一重循環(huán)中枚舉剩下兩個(gè)數(shù)。
首先確定紅色和藍(lán)色的 i 和 j ，然后在剩下的數(shù)中尋找目標(biāo)，向右移動(dòng)綠色的箭頭，直到找到一個(gè)結(jié)果，把這個(gè)結(jié)果存下來(lái)，繼續(xù)移動(dòng)，當(dāng)綠色移動(dòng)結(jié)束后，將藍(lán)色向右移動(dòng)一位，接著移動(dòng)綠色的箭頭進(jìn)行尋找，直到紅色的箭頭移動(dòng)至 num.length - 3 的位置為止。
代碼上我加了注釋，看起來(lái)應(yīng)該比較清晰：
public?class?Solution?{
????public?List>?fourSum(int[]?nums,?int?target)?{
????????List>?result?=?new?ArrayList<>();
????????if?(nums?==?null?||?nums.length?4)?return?result;
????????//?先對(duì)數(shù)組做排序
????????Arrays.sort(nums);
????????int?length?=?nums.length;
????????for?(int?i?=?0;?i?3;?i++)?{
????????????//?特殊情況判斷
????????????//?最小數(shù)字不可重復(fù)
????????????if?(i?>?0?&&?nums[i]?==?nums[i?-?1])?continue;
????????????//?如果和大于?target?，那么接下來(lái)所有的結(jié)果肯定都大于?target?，直接?break
????????????if?(nums[i]?+?nums[i?+?1]?+?nums[i?+?2]?+?nums[i?+?3]?>?target)?break;
????????????//?最大的結(jié)果也小于?target?時(shí)，直接最小數(shù)進(jìn)入下一次循環(huán)
????????????if?(nums[i]?+?nums[length?-?3]?+?nums[length?-?2]?+?nums[length?-?1]?continue;
????????????for?(int?j?=?i?+?1;?j?2;?j++)?{
????????????????//?特殊情況判斷，和最小的數(shù)字判斷規(guī)則相同
????????????????if?(j?>?i?+?1?&&?nums[j]?==?nums[j?-?1])?continue;
????????????????if?(nums[i]?+?nums[j]?+?nums[j?+?1]?+?nums[j?+?2]?>?target)?break;
????????????????if?(nums[i]?+?nums[j]?+?nums[length?-?2]?+?nums[length?-?1]?continue;
????????????????//?left?和?right?分別代表第?3?、4?個(gè)數(shù)
????????????????int?left?=?j?+?1,?right?=?length?-?1;
????????????????while?(left?????????????????????int?sum?=?nums[i]?+?nums[j]?+?nums[left]?+?nums[right];
????????????????????//?當(dāng)結(jié)果和?target?相同時(shí)
????????????????????if?(sum?==?target)?{
????????????????????????//?結(jié)果存入?result?中
????????????????????????result.add(Arrays.asList(nums[i],?nums[j],?nums[left],?nums[right]));
????????????????????????//?去重第三個(gè)數(shù)
????????????????????????while?(left?1])?left++;
????????????????????????left++;
????????????????????????//?去重第四個(gè)數(shù)
????????????????????????while?(left?1])?right--;
????????????????????????right--;
????????????????????}?else?if?(sum?????????????????????????left++;
????????????????????}?else?{
????????????????????????right--;
????????????????????}
????????????????}
????????????}
????????}
????????return?result;
????}
}
