Wednesday, April 9, 2014

Three Sum 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. Bear in mind, the vector need to be sorted first.

Solution:
Same as 3 sum, actually much simpler than 3 sum, since we only need to record the sum result. Update the closet value every time we update the indices. 

Codes:
    int threeSumClosest(vector &num, int target) {
            int close=num[0]+num[1]+num[2];
                sort(num.begin(), num.end());
    for(int i=0; i
    {
        int j=i+1;
        int k=num.size()-1;
        while(j
        {
            int sum2=num[j]+num[k];
            int sum3 = sum2 +num[i];
            if(sum3==target)
                return target;
            else
            {
                if (abs(close-target)>abs(sum3-target))
                    close = sum3;
                if (sum3>target)
                    k--;
                else
                    j++;
            }
        }
    }
    return close;

    }

No comments:

Post a Comment