題目描述
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復的四元組。
注意：答案中不可以包含重復的四元組。
題意：
這道題是求四個數的和相加等于目標值，然后要把重復的值去掉。
這個題的思路和力扣15-三數之和的思路類似，三數之和是固定一個數，其余進行雙指針。四數之和是固定兩個數，其余進行雙指針。
解題思路：
參考官方題解
排序+雙指針：先給數組nums進行升序排序，兩個for循環確定前兩個數，然后使用雙指針確定后兩個數，需要考慮以下幾種情況進行剪枝：
在確定第一個數之后，如果nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target ，代表第一個數與之鄰進的三個最小數之和都大于目標值了，則說明后面剩下的三個數無論取什么值，四數之和一定大于target，則需要退出第一輪循環；
在確定第一個數之后，如果nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target ，代表第一個數與數組中的三個最大數之和都小于目標值了，則說明后面剩下的三個數無論取什么值，四數之和一定小于target，則需要進入下一輪循環，枚舉nums[i+1]；
在確定前兩個數之后，如果nums[i] + nums[j] + nums[j+1] + nums[j+2] > target ，說明剩下的兩個數，無論取什么值，四個數之和一定會大于taret，因此退出第二層循環；
在確定前兩個數之后，如果nums[i] + nums[j] + nums[n-2] + nums[n-1] < target ，說明剩下的兩個數，無論取什么值，四個數之和一定會小于taret，因此進入下一輪，枚舉nums[j+1]；
使用雙指針：左右指針分別指向下標 j+1和下標 n-1。每次計算四個數的和sum，并進行如下操作：
如果和 sum == target，則將枚舉到的四個數加到答案中，然后將左指針右移直到遇到不同的數，將右指針左移直到遇到不同的數；
如果和sum < target，則將左指針右移一位；
如果和sum > target，則將右指針左移一位。
public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<List<Integer>>();int n = nums.length;//如果數組的長度小于4if(n < 4) return res;//對數組進行排序Arrays.sort(nums);//第一個數，只能遍歷到倒數第4位for(int i = 0; i < n-3; i++){//：先去掉重復值if(i > 0 && nums[i] == nums[i-1]) continue;//如果鄰近的四個數大于target,則退出if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;//如果與最大的三個數相加小于target,則說明nums[i]小了，需要進入新一輪循環if((long)nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;//確定第二個數for(int j = i+1; j < n-2; j++){
//去重if(j > i + 1 && nums[j] == nums[j - 1]) continue;if((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;if((long)nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) continue;//確定了兩個數之后，后兩個數使用雙指針int L = j + 1;int R = n - 1;while(L < R){int sum = nums[i] + nums[j] + nums[L] + nums[R];if(sum == target){res.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));//跳過重復數while(L < R && nums[L] == nums[L + 1]) L++;while(L < R && nums[R] == nums[R - 1]) R--;L++;R--;}else if(sum < target){L++;}else{R--;}}}}return res;}
