描述 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).分析 先排序，然后左右夾逼，復雜度 O(n2)。
代碼
class Solution {public: int threeSumClosest(vector<int>& nums, int target) { int min_gap = INT_MAX; int result = 0; sort(nums.begin(), nums.end()); for (auto a = nums.begin(); a != PRev(nums.end(), 2); ++a) { auto b = next(a); auto c = prev(nums.end()); while (b < c) { int sum = *a + *b + *c; int gap = abs(sum - target); if (gap < min_gap) { min_gap = gap; result = sum; } if (sum < target) ++b; else --c; } } return result; }};新聞熱點
疑難解答
