首页 > 代码库 > leetcode第16题--3Sum Closest
leetcode第16题--3Sum Closest
Problem：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).
吃饭之前刷了这题。思路就是和上题类似。先srot，然后固定i从第一个到倒数第三个，然后设一个left=i+1，right=num.size()-1; 如果三个数相加和target相比较大，那就right--，使三个数相加要变小。如果比target小那就left++。同时用abs记录当前的差值，如果比之前的差值更小，那就记录三个数的和到val中。如果差值为零了，那就直接返回三个数的和。否则到最后在返回val就可以了。代码如下class Solution {public:int threeSumClosest(vector<int> &num, int target){ int left = 0, right = 0, val = 0, minC = INT_MAX; sort(num.begin(), num.end()); for (int i = 0; i < num.size() - 2; ++i) { left = i + 1; right = num.size() - 1; while(left < right) { int tepVal = target - num[i] - num[left] - num[right]; if (abs(tepVal) < minC) {minC = abs(tepVal); val = num[i] + num[left] + num[right];} if (tepVal > 0) left++; else if (tepVal < 0) right--; else return num[i] + num[left] + num[right]; } } return val;}};
吃饭去了。
leetcode第16题--3Sum Closest
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。