[array] leetCode-16. 3Sum Closest -Medium
2024-08-31 20:17:47
16. 3Sum Closest -Medium
descrition
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
解析
与 3Sum 的思路一样。不同在于,我们现在希望找到距离 target 最近的数,参看代码。
code
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
class Solution{
public:
int threeSumClosest(vector<int>& nums, int target){
sort(nums.begin(), nums.end()); // ascending
int min_gab = numeric_limits<int>::max();
int ans = target;
for(int i=0; i<nums.size(); i++){
int target_local = target - nums[i];
int ileft = i + 1;
int iright = nums.size() - 1;
while(ileft < iright){ // two pointer searching
int sum = nums[ileft] + nums[iright];
if(sum == target_local) // right answer
return target;
if(sum < target_local) // move ileft to increase sum
ileft++;
else // sum > target_local
iright--;
int gab = abs(sum - target_local);
if(gab < min_gab){
ans = sum + nums[i];
min_gab = gab;
}
}
}
return ans;
}
};
int main()
{
return 0;
}
最新文章
- [译]WebForms vs. MVC
- prototype.js简介
- 南邮CTF隐写之丘比龙的女神
- 固定定位fixed(IE6)
- [转]change the linux startup logo
- 纯后端尝试写一个前端slide插件
- 201521123049 《JAVA程序设计》 第6周学习总结
- day4、Linux基础题目
- 接口测试返回的json文件中字符串是乱序
- PLSQL 登录出现 ora12638 credential retrieval failed
- GIL全局解释器锁
- C++ —— 返回数组指针的函数 和 返回指向函数的指针的函数
- pixel和nexus设备安卓9.0/8.1/7.1.x/6.x WiFi和信号图标出现叉x号或者感叹号的消除办 法
- VOC数据集生成代码使用说明
- angular笔记_6
- 大数据-12-Spark+Kafka构建实时分析Dashboard
- maven自动部署Tomcat错误排除
- 哪些优秀的 Windows 小工具,类似 clover 或 everything
- Java如何获取正在运行的线程的Id?
- centos 安装五笔
热门文章
- WinRAR 5.21 去弹窗 疑惑
- uva 11248 最小割
- ES6第三节:变量的解构赋值
- BZOJ3994: [SDOI2015]约数个数和(莫比乌斯反演)
- 【2017 Multi-University Training Contest - Team 5】Rikka with Subset
- .Net Standard和各平台关系
- 2.2 Consumer API官网剖析(博主推荐)
- 洛谷 P2384 最短路
- Java 学习(16):集合框架
- [D3] Draw a basic US d3-geo map