四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
代码
// 一般代码
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer> > ans = new ArrayList<>();
// 排序
Arrays.sort(nums);
// 穷举遍历，注意去除重复元素
for (int i = 0;i < nums.length - 3;i++) {
// 优化循环
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i+3] > target) { break;}
// i 去重
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1;j < nums.length - 2;j++) {
// 优化循环
if (nums[j] + nums[j + 1] + nums[j + 2] + nums[j + 3] > target) { break;}
// j 去重
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int L = j + 1;
int R = nums.length - 1;
// while (L < R) { // 左右游标法
// int sum = nums[i] + nums[j] + nums[L] + nums[R];
// if (L != j + 1 && nums[L] == nums[L-1] || sum < target) { // 左游标重复 或者 当前和太小
// L++;
// } else if (R != nums.length - 1 && nums[R] == nums[R + 1]
// || sum > target) { // 右游标重复 或者 当前值太大
// R--;
// } else { // 当前值恰好等于目标值
// List<Integer> t = new ArrayList<Integer>();
// t.add(nums[i]);
// t.add(nums[j]);
// t.add(nums[L]);
// t.add(nums[R]);
// ans.add(t);
// // 游标同时移动，是因为移动一个后，当前和肯定不等于目标值。所以必须两个同时移动
// L++;
// R--;
// }
// }
while (L < R) { // 左右游标法
int sum = nums[i] + nums[j] + nums[L] + nums[R];
if (sum < target) { // 当前和太小
L++;
} else if (sum > target) { // 当前值太大
R--;
} else { // 当前值恰好等于目标值
List<Integer> t = new ArrayList<Integer>();
t.add(nums[i]);
t.add(nums[j]);
t.add(nums[L]);
t.add(nums[R]);
ans.add(t);
// 去重
while (L < R && nums[L] == nums[L+1]) { L++;}
while (L < R && nums[R] == nums[R-1]) { R--;}
// 游标同时移动，是因为移动一个后，当前和肯定不等于目标值。所以必须两个同时移动
L++;
R--;
}
}
}
}
return ans;
}
}
// 极优代码
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new LinkedList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j - i > 1 && nums[j] == nums[j - 1]) continue;
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
int left = j + 1;
int right = n - 1;
// 经典的双游标法
while (left < right) {
int tmp = nums[i] + nums[j] + nums[left] + nums[right];
if (tmp == target) {
List<Integer> tmpList = new LinkedList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
res.add(tmpList);
while (left < right && nums[left] == nums[left + 1]) left += 1;
while (left < right && nums[right] == nums[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (tmp > target) right -= 1;
else left += 1;
}
}
}
return res;
}
}
// 作者：powcai
// 链接：https://leetcode-cn.com/problems/two-sum/solution/gu-ding-liang-ge-shu-yong-shuang-zhi-zhen-zhao-lin/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
通解。K数之和 代码
/** 递归回溯
* nums 查找数据集
* target 目标和
* k 求个元素个数
* start 开始下标
*/
public static ArrayList<List<Integer>> kSum(int nums[],int target,int k, int start){
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(start >= nums.length)
return res;
if(k == 2){ // 两数之和
int l = start, h = nums.length - 1;
// 双游标求两数之和
while(l < h){
if(nums[l] + nums[h] == target){
List<Integer> list = new ArrayList<>();
list.add(nums[l]);
list.add(nums[h]);
res.add(list);
while(l<h&&nums[l]==nums[l+1]) // 去重
l++;
while(l<h&&nums[h]==nums[h-1]) // 去重
h--;
l++;
h--;
}else if(nums[l]+nums[h]<target)
l++;
else
h--;
}
return res;
}
if(k > 2){ // 多数之和
for(int i = start;i < nums.length - k + 1; i++){
// 递归实现，求子问题
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
// 回溯处理局部解
if(temp != null) {// k-1个元素的和的解存在
for (List<Integer> l : temp) {
l.add(0, nums[i]); // 将 之前的数字加入到结果集中，构成k个元素和的解
}
res.addAll(temp);// 局部解加到全局解中
}
// 去重
while(i < nums.length-1 && nums[i] == nums[i+1]){
i++;
}
}
return res;
}
return res;
}
// 作者：kukubao207
// 链接：https://leetcode-cn.com/problems/two-sum/solution/kshu-zhi-he-by-kukubao207/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
