最接近的三数之和
原题链接：https://leetcode.cn/problems/3sum-closest/
题目描述
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
三个指针
建议先去看看上一篇文章：两数之和和三数之和。
本题与三数之和的区别是这次限制了target和，而上一次是0。
但是这次，我们不需要去重，直接返回即可。
- 还是创建三个指针：NOW,LEFT,RIGHT
- NOW随循环移动
- LEFT在每轮循环后指向NOW的右侧
- RIGHT在每轮循环后指向数组的最右端
- 对数组排序，便于调整指针位置
- 每轮循环判断
nums[now] + nums[left] + nums[right]与target的关系，具体如何调整，体现在下面的代码中。
上代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int now(0), left(0), right(0);
sort(nums.begin(), nums.end());
int result = nums[0] + nums[1] + nums[2];
for (; now < nums.size() - 1; now++)
{
left = now + 1;
right = nums.size() - 1;
while (left < right)
{
int tmp = nums[now] + nums[left] + nums[right];
if (abs(tmp - target) < abs(result - target))
result = tmp;
if (tmp - target < 0)
{
left++;
}
else if (tmp - target > 0)
right--;
else
return target;
}
}
return result;
}
};运行结果
执行用时：44 ms, 在所有 C++ 提交中击败了58.45%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了42.37%的用户
通过测试用例：98 / 98
四数之和
原题链接：https://leetcode.cn/problems/4sum/
题目描述
给你一个由 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]]
解题思路
在处理两数之和时，我们用到了两个指针，在处理三数之和时，我们用到了三个指针，处理这个四数之和，我们也要用四个指针吗？执行四轮循环，问题的时间复杂度就会非常高。
本题也给了一个target，我们可以将第一轮循环与target做差，做差的结果作为后三轮的target，那么这个问题就变成了三数之和。
本题要求返回所有符合条件的数组，不允许重复，我们需要考虑去重。
在判断四数之和与目标值相等之后，应移动左右指针，跳出重复值
呈上力扣官方的代码
需要强制类型转换，否则会溢出报错
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> quadruplets;
if (nums.size() < 4) {
return quadruplets;
}
sort(nums.begin(), nums.end());
int length = nums.size();
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long)nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long)nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.push_back({ nums[i], nums[j], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
}
}
return quadruplets;
}
};运行结果
执行用时：12 ms, 在所有 C++ 提交中击败了88.62%的用户
内存消耗：12.8 MB, 在所有 C++ 提交中击败了71.27%的用户
通过测试用例：292 / 292
共勉
好好学习，天天向上🚀
