数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最接近的 3Sum
假设有一个包含 n 个整数和一个目标值 target 的数组 nums。我们必须在 nums 中找到三个整数，使得它们的和最接近于目标值。我们将返回这三个整数的和。我们可以假设每个输入都恰好有一个解。所以如果给定的数组像 [-1,2,1,-4] 目标值为 1，那么三元组将是 [-1,2,1]，它具有最接近的和，即 2。
为了解决这个问题，我们将遵循以下步骤：-
- 对数组 nums 进行排序，ans := 0，diff := 无穷大，n := nums 的大小
- 对于从 0 到 n-1 的区间内的 i
- left := i + 1，right := n – 1
- 当 left < right
- temp := nums[left] + nums[right] + nums[i]
- 如果 |target - temp| < diff，那么 ans := temp，diff := |target - temp|
- 如果 temp = target，那么返回 temp，否则当 temp > target 时，right 减 1，否则 left 加 1
- 返回 ans
示例 (C++)
让我们看看以下实现以获得更深入的了解：-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
int diff = INT_MAX;
int n = nums.size();
for(int i = 0; i < n; i++){
int left = i + 1;
int right = n - 1;
while(left < right){
int temp = nums[left] + nums[right] + nums[i];
if(abs(target - temp) < diff){
ans = temp;
diff = abs(target - temp);
}
if(temp == target)return temp;
else if(temp > target) right--;
else left++;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {-1,2,1,-4};
cout << ob.threeSumClosest(v, 1);
}输入
[-1,2,1,-4] 1
输出
2
更新于: 2020 年 4 月 27 日
1000 多次浏览
广告