题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。 
解题思路：
最朴素的方法是使用四重循环枚举所有的四元组，然后使用哈希表进行去重操作，得到不包含重复四元组的最终答案。假设数组的长度是 nnn，则该方法中，枚举的时间复杂度为 O(n^4)，去重操作的时间复杂度和空间复杂度也很高，因此需要换一种思路。
为了避免枚举到重复四元组，则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素。
为了实现上述要求，可以对数组进行排序，并且在循环过程中遵循以下两点：
每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。
使用上述方法，可以避免枚举到重复四元组，但是由于仍使用四重循环，时间复杂度仍是 O(n^4)。注意到数组已经被排序，因此可以使用双指针的方法去掉一重循环。
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { // 两数之和 // 排序 + 双指针 // 或者 使用哈希表 // 三数之和 // 排序 + 遍历确定第一个数字 + 双指针 // 四数之和 // 排序 + 遍历确定前两个数字 + 双指针 // a,b,c,d 四个数字需要互不相同 // 且四元组不能重复 int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); for(int a = 0;a < n - 3;a ++) { // 确定 a // 如果 nums[a] == nums[a-1] 则跳过 // 因为这时对于 nums[a] 满足的 b,c,d // 对于 nums[a-1] 也一定满足 if(a > 0 && nums[a] == nums[a-1]) { continue; } if(0L + nums[a] + nums[a+1] + nums[a+2] + nums[a+3] > target) { // 如果当前 a 对应最小的四元组之和都大于 target // 那么当前 a 对应的四元组都不满足需求 // 并且 a 往右遍历, nums[a] 是增大的 // 那么以后的 a 更不满足需求, 可以提前结束了 return ans; }else if(0L + nums[a] + nums[n-1] + nums[n-2] + nums[n-3] < target) { // 如果当前 a 最大的四元组都小于 target // 那么当前 a 对应的四元组都不满足需求 // 之后遍历的 a ,nums[a] 会变大 有可能满足需求 // 因此跳过当前轮次 continue; } for(int b = a + 1; b < n - 2;b ++) { // 确定 b if(b > a+1 && nums[b] == nums[b-1]) { continue; } if(0L + nums[a] + nums[b] + nums[b+1] + nums[b+2] > target) { // 如果当前 b 对应的最小的大于 target // 那么当前 b 对应的其它四元组也必定大于 target // 而且 a 不变的情况下 b 往右遍历 只会得到更大的四元组 // 对于下一个 a , b 会变小 可能会满足需求 // 因此需要跳过当前 a break; } else if(0L + nums[a] + nums[b] + nums[n-1] + nums[n-2] < target) { // 如果当前 b 对应最大的四元组小于 target // 当前 b 对应的其它四元组也是小于 target // 而下一个 b 会增大,有可能满足需求 continue; } int c = b + 1, d = n - 1; long sumAB = nums[a] + nums[b]; while(c < d) { if(sumAB + nums[c] + nums[d] == target) { // 加入答案 ans.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d])); c ++; while(c < d && nums[c] == nums[c-1]) { // 过滤掉重复的 c // 因为 nums[a] nums[b] 已经确定 // nums[c] 如果再相同, // 就会产生重复的四元组 c ++; } d --; while(c < d && nums[d] == nums[d + 1]) { // 过滤掉重复的 d d --; } } else if(sumAB + nums[c] + nums[d] < target) { c ++; } else { d --; } } } } return ans; } }
