[LeetCode] 16. 3Sum Closest 最近三数之和 All LeetCode Questions List 题
Given an arraySofnintegers, find three integers inSsuch 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).
15. 3Sum 三数之和的拓展,这题是让找到和目标数最接近的数字组合,还是用3Sum的方法,只是这次要设一个变量minDif来记录最小差值的绝对值,如果当前三数的和与目标数的差的绝对值小于minDif则此组合更接近目标数,result变为此组合的和,迭代查找直到结束, 返回result。
C++:
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int closest = nums[0] + nums[1] + nums[2]; int diff = abs(closest - target); sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() - 2; ++i) { int left = i + 1, right = nums.size() - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; int newDiff = abs(sum - target); if (diff > newDiff) { diff = newDiff; closest = sum; } if (sum < target) ++left; else --right; } } return closest; } };
All LeetCode Questions List 题目汇总
相关推荐
csdnliuy 2011-11-10
AnneZhao 2015-07-01
XiaoSpring 2013-11-28
85173253 2013-10-11
83453065 2013-08-17
崔博伦一路有你 2012-08-14
yyzhu 2012-06-18
快乐就好 2016-06-21
gentlemanhua 2016-04-14
牵手白首 2016-04-14
nnj 2019-04-21
xiongfeng 2015-03-17
nnj 2014-04-09
yaasshole 2013-12-02
melissahexiu 2013-04-26
87384559 2011-05-18
舜岳 2009-12-14