三数之和与四数之和 | LeetCode-15 | LeetCode-18 | 双指针 | 降维 | 哈希集合 | Java | 详细注释

🍏去重和🍓降维是这两道题的关键！

题目1：三数之和🍇

1.题目描述🍉

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• $-10^5<=nums[i]<=10^5$

2.题解🍋

2.1 双指针🍑

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 对数组进行排序，方便后续使用双指针方法寻找满足条件的三元组Arrays.sort(nums);// 用于存放所有满足条件的三元组结果List<List<Integer>> resultList = new ArrayList<>();int n = nums.length;// 第一层循环，选择第一个数for (int first = 0; first < n - 2; first++) {// 如果当前数字大于0，则不可能有三元组和为0，因为数组已排序if (nums[first] > 0) break;// 跳过重复的数字以避免添加重复的三元组if (first > 0 && nums[first] == nums[first - 1]) continue;// 定义双指针，second 从 first+1 开始，third 从数组末尾开始int second = first + 1, third = n - 1;// 双指针查找当前first对应的所有满足条件的三元组while (second < third) {// 计算三数之和int sum = nums[first] + nums[second] + nums[third];// 如果和为0，找到一个满足条件的三元组if (sum == 0) {List<Integer> list = new ArrayList<>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);resultList.add(list);//resultList.add(Arrays.asList(nums[first], nums[second], nums[third]));// 去重：移动second和third指针以跳过重复的数字while (second < third && nums[second] == nums[second + 1]) second++;while (second < third && nums[third] == nums[third - 1]) third--;// 移动指针，继续寻找其他可能的三元组second++;third--;} else if (sum > 0) {// 如果和大于0，说明third指向的值太大，移动third指针减小总和third--;} else {// 如果和小于0，说明second指向的值太小，移动second指针增加总和second++;}}}// 返回所有找到的三元组列表return resultList;}
}

题目2：四数之和🍎

1.题目描述🍍

给你一个由 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
• $-10^9<=nums[i]<=10^9$
• $-10^9<=target<=10^9$

2.题解🥝

2.1 双指针🥥

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {// 对数组进行排序，方便后续使用双指针方法寻找满足条件的四元组Arrays.sort(nums);// 用于存放所有满足条件的四元组结果List<List<Integer>> resultList = new ArrayList<>();int n = nums.length;// 第一层循环，选择第一个数for (int first = 0; first < n - 3; first++) {// 跳过重复的数字以避免添加重复的四元组if (first > 0 && nums[first] == nums[first - 1]) continue;// 第二层循环，选择第二个数for (int second = first + 1; second < n - 2; second++) {// 跳过重复的数字以避免添加重复的四元组if (second > first + 1 && nums[second] == nums[second - 1]) continue;// 定义双指针，third 从 second+1 开始，fourth 从数组末尾开始int third = second + 1;int fourth = n - 1;// 双指针查找当前first和second对应的所有满足条件的四元组while (third < fourth) {// 计算四数之和，使用long以防止整数溢出long sum = (long) nums[first] + nums[second] + nums[third] + nums[fourth];// 如果和等于目标值，找到一个满足条件的四元组if (sum == target) {List<Integer> list = new ArrayList<>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);list.add(nums[fourth]);resultList.add(list);// 去重：移动third和fourth指针以跳过重复的数字while (third < fourth && nums[third] == nums[third + 1]) third++;while (third < fourth && nums[fourth] == nums[fourth - 1]) fourth--;// 移动指针，继续寻找其他可能的四元组third++;fourth--;} else if (sum > target) {// 如果和大于目标值，说明fourth指向的值太大，移动fourth指针减小总和fourth--;} else {// 如果和小于目标值，说明third指向的值太小，移动third指针增加总和third++;}}}}// 返回所有找到的四元组列表return resultList;}
}

• 优化：

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {// 对数组进行排序，方便后续使用双指针方法寻找满足条件的四元组Arrays.sort(nums);// 用于存放所有满足条件的四元组结果List<List<Integer>> resultList = new ArrayList<>();int n = nums.length;// 第一层循环，选择第一个数for (int first = 0; first < n - 3; first++) {// 1级剪枝处理if(nums[first] > target && nums[first] >0) break;// 跳过重复的数字以避免添加重复的四元组if (first > 0 && nums[first] == nums[first - 1]) continue;// 第二层循环，选择第二个数for (int second = first + 1; second < n - 2; second++) {// 2级剪枝处理if (nums[first] + nums[second] > target && nums[first] + nums[second] >= 0) break;// 跳过重复的数字以避免添加重复的四元组if (second > first + 1 && nums[second] == nums[second - 1]) continue;// 定义双指针，third 从 second+1 开始，fourth 从数组末尾开始int third = second + 1;int fourth = n - 1;// 双指针查找当前first和second对应的所有满足条件的四元组while (third < fourth) {// 计算四数之和，使用long以防止整数溢出long sum = (long) nums[first] + nums[second] + nums[third] + nums[fourth];// 如果和等于目标值，找到一个满足条件的四元组if (sum == target) {resultList.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));// 去重：移动third和fourth指针以跳过重复的数字while (third < fourth && nums[third] == nums[third + 1]) third++;while (third < fourth && nums[fourth] == nums[fourth - 1]) fourth--;// 移动指针，继续寻找其他可能的四元组third++;fourth--;} else if (sum > target) {// 如果和大于目标值，说明fourth指向的值太大，移动fourth指针减小总和fourth--;} else {// 如果和小于目标值，说明third指向的值太小，移动third指针增加总和third++;}}}}// 返回所有找到的四元组列表return resultList;}
}