Friday, June 14, 2013

Leetcode: 3Sum Closest in C++



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


Solution:
int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int len = num.size();
        int cloest = INT_MAX;
        int sum =0;
        int left =0;
        int right = len-1;
        int result = 0;
        for(int i=0;i<len-2;i++)
        {
            left = i+1;
            right = len-1;
            while(left<right)
            {
                sum = num[left]+num[i]+num[right];
                if(sum==target)
                   return sum;
                else if(sum>target)
                   right--;
                else
                   left++;
                if(abs(sum-target)<cloest)
                {
                   cloest = abs(sum - target);
                   result = sum;
                }
            }
            
        }
        return result;
    }

No comments:

Post a Comment