一、原題

給你一個由?n?個整數(shù)組成的數(shù)組?nums?，和一個目標值?target?。請你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個四元組元素一一對應(yīng)，則認為兩個四元組重復(fù)）：

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

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

示例 1：

輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]

二、心得

? ? ? ? 前有三數(shù)之和，今有四數(shù)之和~

? ? ? ? 整體思路和三數(shù)之和一致：排序 + 指針。只是這題多了一個會動的指針，即第四者。

? ? ? ? 代碼 + 注釋完美配合（不想多說什么了~）：

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();// 判斷為空及長度為0的情況if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums); // 排序int length = nums.length;// 第一個數(shù) nums[i]，由于有四個數(shù)，注意遍歷范圍for (int i = 0; i < length - 3; i++) {// 避免重復(fù)的元素，遇到則跳過if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 如果連續(xù)相鄰的四個數(shù)（此時考慮的是全部都在最左側(cè)）之和大于 target，說明此時再也無法找到符合要求的組合了，直接 breakif ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}// 如果四個數(shù)（此時考慮的是在最右側(cè)）之和小于 target，說明 nums[i] 此時偏小，還可以向后遍歷，即循環(huán)還可以繼續(xù)if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}// 第二個數(shù) nums[j]，確保在 nums[i] 后面，注意遍歷范圍，應(yīng)至少預(yù)留兩個位置，即 length - 2for (int j = i + 1; j < length - 2; j++) {// 避免重復(fù)的元素 if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}// 同樣左側(cè)四個數(shù)的情況if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}// 四個數(shù)右側(cè)情況if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}// 第三個數(shù) nums[left]，保證在 nums[j] 后面，第四個數(shù) nums[right] 從末端開始向前遍歷int left = j + 1, right = length - 1;// 確定符合情況的四元數(shù)，添加到總列表中while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 避免重復(fù)的元素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++; // 因為 sum 小于目標值，表明接近負數(shù)的 nums[left] 比較小，應(yīng)向后遍歷} else {right--; // 因為 sum 大于等于目標值，表明接近正數(shù)的 nums[right] 比較大，應(yīng)向前遍歷}}}}// 返回總列表return quadruplets;}
}

? ? ? ? 不知道有沒有小伙伴忘記是怎么一個回事了？且看下圖回憶回憶：

? ? ? ? 補：long 64位 ，范圍為?

? ? ? ? 這種類型的題越來越熟練了，嘿嘿(●ˇ?ˇ●)~