sundeepblue
5/1/2014 - 12:08 AM

[array] 3sum closest. Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Retur

[array] 3sum closest. 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.

three_sum_closest.cpp
content_copyfile_download
int three_sum_closest(vector<int>& A, int key) {
    if(A.empty()) return -1;
    sort(A.begin(), A.end());
    int i = 0, N = A.size();
    int close_sum;
    int diff = INT_MAX;
    while(i <= N-3) {
        int j = i+1, k = N-1;
        while(j < k) {
            long long sum = A[i] + A[j] + A[k];
            if(sum == key) return sum;
            
            if(diff > abs(sum - key)) {
                diff = abs(sum - key);
                close_sum = sum;
            }
            
            if(sum < key) j++;
            else if(sum > key) k--;
        }
        i++;
    }
    return close_sum;
}

int main()
{
    vector<int> A = {1,2,3,4,5};
    cout << three_sum_closest(A, 4);
}