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. http://www.leetcode.com/onlinejudge

leetcode_3sum_closest.cpp

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void update(int& closest, int& ret, int sum, int target) {
        int diff = abs(sum - target);
        if (diff < closest) {
            closest = diff;
            ret = sum;
        }
    }
    
    int threeSumClosest(vector<int> &num, int target) {
        int closest = 0x7fffffff;
        int ret = 0;
        sort(num.begin(), num.end());
        for (int i = 0; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size() - 1; ++j) {
                int find = target - num[i] - num[j];
                // binary search
                int left = j + 1;
                int right = num.size() - 1;
                int tmp = right;
                while (left <= right) {
                    int mid = (left + right) >> 1;
                    if (num[mid] >= find) {
                        right = mid - 1;
                        tmp = min(mid, tmp);
                    }
                    else {
                        left = mid + 1;
                    }
                }
                // calculate sum
                int sum = num[i] + num[j] + num[tmp];
                update(closest, ret, sum, target);
                if (tmp - 1 > j) {
                    sum = num[i] + num[j] + num[tmp - 1];
                    update(closest, ret, sum, target);
                }
            }
        }
        return ret;
    }
};