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