Three Sum Closest

LeetCode #16

Description:

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.

Example:

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

Idea:

先排序，然后左右夹逼，Time 复杂度 O(n2)。

Code:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int min_gap=INT_MAX;
        int three_sum=0;
        int close_sum;

        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size()-2; ++i){
            int j=i+1;
            int k=nums.size()-1;

            while(j<k){
                three_sum = nums[i]+nums[j]+nums[k];

                if(abs(target-three_sum)<min_gap){
                    min_gap = abs(target-three_sum);
                    close_sum = three_sum;
                } 

                if(three_sum == target){
                    return target;
                }
                else if(three_sum < target){
                    j++;
                }
                else{
                    k--;
                }
            }
        }

        return close_sum;
    }
};