文档讲解：代码随想录
难度：有一点点难度
附：寒假继续开始刷题更新刷题记录
passion！！！passion！！！passion！！！
第18题. 四数之和
力扣题目链接(opens new window)
题意：给定一个包含 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] ]
思路
可以将问题简单化：往期刷过两数之和和三数之和，所以可以尝试将四数之和转换为三数之和，三数之和的解题的一个巧妙思路如下：
为了降低时间复杂程度，可以对一些可以直接排除的元素进行去除：三数之和中如果一个数字大于目标数字，则可以直接去除（由于已知目标是0，故第一个数字不可以大于目标数字）
详细参考以下文档：
代码随想录
第15题. 三数之和
也可以参考本人往期作品中的“三数之和”
代码随想录算法训练营第十一天|383. 赎金信， 15. 三数之和
- 由于题目并没有表明该数组是有序k数组，故应先对数组进行排序（sort方法）；
- 进入循环1.1（k）
- 同理，对一些元素直接排除：因为目标的大小正负未知，故应该加一些条件：如果一个数字大于目标，但为了避免出现特殊情况（如num[k]=-4,目标是-10，）应该对该数字和目标进行正负分析并添加验证条件，可以判断 目标数字或num[k]的正负， 最后为代码实现为nums[i] > target && (nums[i] >=0 || target >= 0)
- 去除相同的数字（题目要求），因为已经进行了排序，故判断该数字的前（后）即可
- 进入循环2.1（i）（2代表为内层，.1代表是内层第一次循环，以下同理）
- 进行第二次进入步骤2，3（可以理解为将前两个数字和并为一个整体后，再进行一次判断）
- 设置左右指针，左指针为i的下一个元素，右指针为num数组的最后一个元素
- 进入循环3.1（判断条件为右指针应该大于左指针）
- 求四数之和：sum=num[k]+num[i]+num[left]+num[right],如果sum偏大则将右指针左移动（排序后，右侧数大于左侧），如果sum偏小则将左指针右移动，如果符合则将num[k]，num[i]，num[left]，num[right]计入result数组
- 进入循环4.1，4.2再次进行步骤4进行去重
- 左右指针都向中移动
- 所有循环结束返回result数组
- 定义测试部分：
补充
在Java中，foreach循环也被称为增强型for循环。它可以用来遍历数组、集合或其他类似结构的数据。foreach循环的语法如下：
for (element_type element : collection) {
// 循环体
}
其中，element_type是集合中元素的类型，element是集合中每个元素的变量名，collection是需要遍历的集合。在循环体中，可以使用element变量来访问当前元素的值。
下面是一个示例，展示了如何使用foreach循环来遍历一个整型数组：
int[] numbers = {1, 2, 3, 4, 5};
for (int number : numbers) {
System.out.println(number);
}
在这个示例中，我们定义了一个整型数组numbers，然后使用foreach循环来遍历这个数组，并在循环体中打印出每个元素的值。输出结果如下：
除了数组，foreach循环还可以用于遍历其他类型的集合，例如List、Set、Map等。不过需要注意的是，对于Map类型的集合，foreach循环只能遍历其中的键或值，而不能同时访问键和值。
代码如下：
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums); // 排序数组
List<List<Integer>> result = new ArrayList<>(); // 放结果
for (int k = 0; k < nums.length; k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 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 (right > left) {
long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
List<List<Integer>> results = solution.fourSum(nums, target);
for (List<Integer> result : results) {
System.out.println(result);
}
}
}
