最接近的三数之和
原题链接：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
共勉
好好学习，天天向上🚀
