3Sum Closest

Question：
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).
 
Anwser 1：  O（n^2）
[cpp]  
class Solution {  
public:  
    int threeSumClosest(vector<int> &num, int target) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        int len = num.size();  
        assert(len >= 3);  
          
        vector<int> num2;  
        num2.assign(num.begin(), num.end());  
          
        sort(num2.begin(), num2.end());  
          
        int sum = num2[0] + num2[1] + num2[2];  
        int diff = abs(sum - target);  
        int ret = sum;  
          
        for(int i = 0; i < len - 2; i++){  
            int l = i + 1;  
            int r = len - 1;  
              
            while(l < r){  
                sum = num2[i] + num2[l] + num2[r];  
                  
                if(sum == target) {  
                    return sum;  
                } else if (sum < target){  
                    l++;  
                } else {  
                    r--;  
                }  
                  
                if(abs(sum - target) < diff){       // more close, refresh diff and ret  
                    diff = abs(sum - target);  
                    ret = sum;  
                }  
            }  
        }  
        return ret;  
    }  
};  
 
 
 
参考推荐：
3Sum
4Sum
数组中最大和的子数组
 

补充：软件开发 , C++ ,

上一个：Plus One
下一个：sqrt(int x)