Leetcodes Solutions 16 3Sum closest

zhuanlan.zhihu.com

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

思路1

遍歷的過程類似3Sum，只是要找的目標是一個給定的值，而且返回的是三個數求和後，離給定值最近的值。

class Solution{public: int threeSumClosest(vector<int> &num, int target){ vector<int> v(num.begin(), num.end()); //not to disturb the original array int n = 0; int ans = 0; int sum; sort(v.begin(), v.end()); //if less than 3 elements then return their sum while(v.size() <= 3) return accumulate(v.begin(), v.end(), 0); n = v.size(); ans = v[0] + v[1] + v[2]; for(int i = 0; i < n - 2; i++){ int j = i + 1; int k = n - 1; while(j < k){ sum = v[i] + v[j] + v[k]; if(abs(target - ans) > abs(target - sum)){ //ans到target的距離大於sum到target的距離 ans = sum; if(ans == target) return ans; } (sum > target) ? k-- : j++; } } return ans; }};

推薦閱讀：