两数之和、三数之和、四数之和
目录
两数之和
题目链接
题目描述
思路分析
代码实现
三数之和
题目链接
题目描述
思路分析
代码实现
四数之和
题目链接
题目描述
思路分析
代码实现
两数之和
题目链接
LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
题目描述
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]
示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61 输出：[27,34] 或者 [34,27]
思路分析
题目要求我们找到两个价格之和刚好为 target 的商品，且只需要返回任意一组结果
我们可以使用暴力枚举的方式，列出所有的两个数字的组合，判断这两个数字的和是否等于目标值
但是，此时的时间复杂度为 O(N^2)，且会超时
由于数组是升序的，因此，我们可以使用 对撞指针 来解决这个问题
我们定义两个指针，分别指向数组的最左端和最右端
若 nums[left] + nums[right] < target，此时 nums[right] 为最大值，不能再增加了，因此我们需要让 nums[left] 变大，因此 left++，让 nums[left] 增加
若 nums[left] + nums[right] > target，此时 nums[left] 为最小值，不能再减小了，因此，我们让 right--，减小 nums[right] 的值，从而让两数之和减小
若 nums[left] + nums[right] = target，说明找到结果了，记录结果并返回即可
接下来，我们就来尝试编写代码
代码实现
class Solution {
public int[] twoSum(int[] price, int target) {
int len = price.length;
int left = 0, right = len - 1;
while(left < right) {
if (price[left] + price[right] < target) {
left++;
} else if(price[left] + price[right] > target) {
right--;
} else {
return new int[] {price[left], price[right]};
}
}
return new int[2];
}
}三数之和
题目链接
15. 三数之和 - 力扣（LeetCode）
题目描述
给你一个整数数组 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 。
思路分析
题目要求我们找到 所有和为 0 且不重复的三元组，相比于上述的两数之和，此时我们要找到所有和为0的三元组，且不能重复
我们同样可以利用 对撞指针 的思想来解决这个问题
由于数组不是有序的，因此，我们先对其进行排序
接着，由于要找三个数，因此，我们可以先固定一个数 nums[k]，此时就需要找到两个数，它们的和 target 为 -nums[k]
若 nums[left] + nums[right] < target，left++
若 nums[left] + nums[right] > target，right--
若 nums[left] + nums[right] = target，找到一组和为 0 的三元组，但是，在 [left + 1, right - 1] 区间内可能还存在和为 target 的二元组，因此 left++，right--
但是，由于不能出现重复的三元组，因此，我们需要对其进行 去重 操作
当找到一个结果时，left 和 right 都需要跳过重复的元素
此外，当结束完一次循环后，固定的 k 也需要进行去重操作
在分析完解题思路之后，我们就来尝试编写代码解决问题
代码实现
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
List<List<Integer>> ret = new ArrayList<>();
// 对元素进行排序
Arrays.sort(nums);
for(int i = 0; i < len - 2; ) {
int target = 0 - nums[i];
int left = i + 1;
int right = len - 1;
while(left < right) {
int sum = nums[left] + nums[right];
if(sum > target) {
right--;
} else if(sum < target) {
left++;
} else {
ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
// 继续找
left++;
right--;
// 去重
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
while(left < right && nums[right] == right + 1) {
right--;
}
}
}
// 去重
i++;
while(i < len && nums[i] == nums[i - 1]) {
i++;
}
}
return ret;
}
}四数之和
题目链接
18. 四数之和 - 力扣（LeetCode）
题目描述
给你一个由 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）对数组进行排序
（2）固定a 位置的数
（3）在数a的前面区间上，利用三数之和找到三个数，使得这三个数的和等于 target - nums[a] 即可
代码实现
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ret = new ArrayList<>();
int len = nums.length;
if(len < 4) {
return ret;
}
// 排序
Arrays.sort(nums);
int i = 0;
while(i < len - 3) {
int j = i + 1;
while(j < len - 2) {
int left = j + 1;
int right = len - 1;
long t = (long)target - nums[i] - nums[j];
while(left < right) {
if(nums[left] + nums[right] < t) {
left++;
} else if(nums[left] + nums[right] > t){
right--;
} else {
ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
// 去除左边重复元素
left++;
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
// 去除右边重复元素
right--;
while(left < right && nums[right] == nums[right+1]) {
right--;
}
}
}
j++;
while(j < len - 2 && nums[j] == nums[j - 1]) {
j++;
}
}
i++;
while(i < len - 3 && nums[i] == nums[i - 1]) {
i++;
}
}
return ret;
}
}