题目：
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.
标签：
Array
体会：
1. 这道题最直接的想法肯定是想 A3n的那种解法，就是遍历所有可能的三个数的排列，然后找结果。可是这样就是A3n = n(n-1)(n-2) = O(n3)的解法，会exceed time limit。
2. 然后就是低于3次的解法了。
class Solution { public: int threeSumClosest(vector<int> &num, int target) { // we don‘t want to change the original vector probably // how to declare vector in C++ vector<int> v(num.begin(), num.end()); int result = 0; int size = v.size(); if (size <= 3) { for (int i = 0; i < size; i++){ result += v[i]; } return result; } std::sort(v.begin(), v.end()); result = v[0] + v[1] + v[2]; int sum = 0; for (int i = 0; i < size - 2; i++) { int j = i + 1; int k = size - 1; while (j < k) { sum = v[i] + v[j] + v[k]; if (std::abs(target - sum) < std::abs(target - result)) { result = sum; if (result == target) { return result; } } if (sum > target) { k--; } else { j++; } } } return result; } };
原文：http://www.cnblogs.com/stevencooks/p/4047755.html