【leetcode】3Sum Closest(middle)

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).

思路:

先排序,然后固定一个边界,另外两个边界收缩。

class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int l, r, m;
int ans = num[] + num[] + num[];
sort(num.begin(), num.end()); //数字从小到大排序
for(l = ; l < num.size() - ; l++) //固定左边界
{
m = l + ;
r = num.size() - ;
while(m < r) //收缩中间和右边界
{
int tmp = num[l] + num[m] + num[r];
ans = (abs(ans - target) > abs(tmp - target)) ? tmp : ans;
if(tmp < target)
{
(num[m] > num[r]) ? r-- : m++; //比目标小 则把小的数字变大
}
else if(tmp > target)
{
(num[m] < num[r]) ? r-- : m++; //比目标大 则把大的数字变小
}
else
{
return tmp; //已经等于target就直接返回
}
}
}
return ans;
}
};
上一篇:CF459E Pashmak and Graph (DP?


下一篇:atmega32u4制作arduino leonardo最小系统