问题

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

分析

类似于3Sum -

解答

int threeSumClosest(std::vector<int>& nums, int target) { int closestLen=INT_MAX; int result = 0; if (nums.size() <= 3){ for (int i = 0; i < nums.size(); i++) result += nums[i]; return result; } sort(nums.begin(), nums.end()); for (std::vector<int>::iterator i = nums.begin(); i < nums.end()-2; i++){ std::vector<int>::iterator start = i + 1; std::vector<int>::iterator end = nums.end() - 1; if (i != nums.begin() && *(i - 1) == *i){ continue; } while (start < end){ if ((*start + *end+ *i)== target){ return target; } else if ((*start + *end+*i) > target){ if (((*start + *end + *i) - target) <closestLen){ closestLen = (*start + *end + *i) - target; result = (*start + *end + *i); } end--; } else{ if ((target - (*start + *end + *i)) <closestLen){ closestLen = target - (*start + *end + *i); result = (*start + *end + *i); } start++; } } } return result; }