1 题目地址
18. 四数之和 - 力扣（LeetCode）18. 四数之和 - 给你一个由 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
https://leetcode.cn/problems/4sum/description/
2 题目说明
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、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
3 解题思路
四数之和思路和三数之和思路类似，在三数之和的基础上再套一层for循环；三数之和双指针解决是一层for循环nums[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
那么一样的道理，五数之和、六数之和等等都采用这种解法。
流程：
1、初始时：定义指针k指向第0个元素，指针i指向k+1,;
指针left指向i+1, 指针right指向nums.length-1位置
2、如果nums[k]>target && target>=0；则直接break；进入下一次循环，也可以直接返回结果
【数据最小的元素大于target，并且target>=0；多数相加自然会更大于target】【剪枝】
3、如果nums[k]+nums[i]>target && nums[k]+nums[i] >0; 则本轮(i)，不会有符合条件的数据。
【两数相加大于target，则四数相加更大于target，target是正数的情况下】 【剪枝】
4、nums[k] + nums[i] + nums[left] + nums[right] > target；right--; nums[right]变小，整体变小
5、nums[k] + nums[i] + nums[left] + nums[right] < target; left++; nums[left]变大，整体变大
6、nums[k] + nums[i] + nums[left] + nums[right] == target; left++; right--；
记录结果并移动left、right
7、去重： i k left right
k>0 && nums[k]==nums[k-1]; 向右移动k++;
i>k+1 && nums[i]==nums[i-1]; 向右移动i++;
left < right && nums[left]==nums[left-1]; 向右移动left++;
left > right && nums[right]==nums[right+1]; 向左移动right--
4 代码编写
4.1 双指针法
class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> resultList = new ArrayList<>();// 排序Arrays.sort(nums);for (int k=0; k<nums.length; k++) {if (nums[k] > target && target>=0) {break; // 跳出本层循环}// 对nums[k]去重if (k > 0 && nums[k] == nums[k - 1]) {continue;}for (int i=k+1; i<nums.length; i++) {if (nums[k]+nums[i]>target && nums[k]+nums[i]>0) {break; // 跳出本层循环}// 对nums[i]去重if (i > k + 1 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (left < right) {int result = nums[k]+nums[i]+nums[left]+nums[right];if (result>target) {right--;} else if ( result<target){left++;} else {resultList.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));while (left<right && nums[left]==nums[left+1]) left++;while (left<right && nums[right]==nums[right-1]) right--;left++;right--;}}}}return resultList;}
}