leetcode 3sum closest

左右夹逼法(先排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class  {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = 0;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
auto last = nums.end();
for(auto i = nums.begin(); i < last - 2; ++i) {
auto j = next(i);
auto k = last - 1;
while(j < k) {
const int sum = *i + *j + *k;
const int gap = abs(sum - target);
if(gap < min_gap) {
min_gap = gap;
res = sum;
}
if(sum > target) {
k--;
}else {
j++;
}
}
}
return res;
}
};