最接近的三数之和

原题链接：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。

但是这次，我们不需要去重，直接返回即可。

1. 还是创建三个指针：NOW,LEFT,RIGHT
2. NOW随循环移动
3. LEFT在每轮循环后指向NOW的右侧
4. RIGHT在每轮循环后指向数组的最右端
5. 对数组排序，便于调整指针位置
6. 每轮循环判断nums[now] + nums[left] + nums[right]与target的关系，具体如何调整，体现在下面的代码中。

上代码

class Solution { public:  int threeSumClosest(vector& 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> fourSum(vector& nums, int target) {  vector<vector> 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

共勉

好好学习，天天向上