题目描述：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
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]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
解题思路：
双指针法铺垫： 先将给定 nums 排序，复杂度为 O(NlogN)。
双指针法思路： 固定 4个指针中最左数字的指针 i，j，双指针 left，right 分设在数组索引 (j+1, nums.length-1) 两端，
通过双指针交替向中间移动，记录对于每个固定指针 i, j的所有满足 nums[i] + nums[j] + nums[left] + nums[right] == target 的 left, right合：
1、第一层循环，开始标志为i = 0, 结束标志为i < nums.length - 3,因为要和另外三个指针j, left, right流出空间,如果i > 0并且nums[i] == nums[i-1]跳过此次循环；
2、第二层循环，开始标志为j= i+1, 结束标志为j < nums.length -2,因为要和另外两个指针left, right流出空间,如果j> i+1并且nums[j] == nums[j-1]跳过此次循环；
3、left, right 分设在数组索引(j+1, nums.length-1) 两端，当left < right时循环计算sum = nums[i] + nums[j] + nums[left] + nums[right]，并按照以下规则执行双指针移动：
3.1: 当sum < target时，left += 1并跳过所有重复的nums[left]；
3.2: 当sum > target时，right -= 1并跳过所有重复的nums[right]；
3.3: 当sum == 0时，记录组合[i, j, left, right]至list中，执行left += 1和right -= 1并跳过所有重复的nums[left]和nums[right]，防止记录到重复组合。
复杂度分析：
时间复杂度 O(N^2)：其中固定指针k循环复杂度O(N)，双指针 left，right复杂度 O(N)。
空间复杂度 O(1)：指针使用常数大小的额外空间。
解析参考链接：https://leetcode-cn.com/problems/4sum/solution/si-wei-dao-tu-zheng-li-xiang-xi-zhu-jie-292hq/
代码实现：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FourSum {
public static void main(String[] args) {
int[] nums = {2, 2, 2, 2, 2};
System.out.println(fourSum(nums, 8));
}
// 方法1：排序 + 双指针
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> listList = new ArrayList<>();
// 1. 如果数组元素小于4，直接返回空的集合
if(nums.length < 4){
return listList;
}
// 2. 对数组中元素进行排序
Arrays.sort(nums);
// 3. 两层for循环 + 双指针：i, j, left, right
for(int i = 0; i < nums.length-3; i++){
// 3.1 去重
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j = i+1; j < nums.length-2; j++){
// 3.2 去重
if(j > i+1 && nums[j] == nums[j-1]) continue;
// 3.1 声明左右指针
int left = j+1, right = nums.length-1;
while (left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target){
List<Integer> list = new ArrayList<>();
Collections.addAll(list, nums[i] , nums[j] , nums[left] , nums[right]);
if(!listList.contains(list)){
listList.add(list);
}
while (left < right && nums[right] == nums[--right]); // 右指针向左移动并去重
while (left < right && nums[left] == nums[++left]); // 左指针向右移动并去重
}else if(sum > target){
while (left < right && nums[right] == nums[--right]); // 右指针向左移动并去重
}else {
while (left < right && nums[left] == nums[++left]); // 左指针向右移动并去重
}
}
}
}
return listList;
}
}
收获：
1、此题的优化思想非常重要，是在三数之后的基础上提出来的，三数之和弄懂了此题就很容易解决，优化思想就是如何去重复；
2、目前初始才开始刷题阶段先不要想着优化，先达到第一阶段能够成功的跑通代码就可以，到后面的二刷或者三刷的时候才尽可能关注优化问题。
3、第一阶段任务：无论通过何种方式撸代码也好或者调用API也好只要能够解决问题就好！！！！
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
