Tuesday, April 29, 2014

3 Sum Closest -- Leetcode

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

Answer:
Similar to "3 Sum", additionally add a minv to track |a+b+c-target|, find the smallest value.

class Solution {
public:
  int threeSumClosest(vector<int> &num, int target) {
    int minv = INT_MAX, res;
    int flag = 0;
    sort(num.begin(), num.end());
   
    for (int i = 0;i < num.size(); i++) {
        if(i>0 && num[i]==num[i-1]) continue;
       
        int j = i + 1;
        int k = num.size() - 1;
        while (j < k) {
            int sum = num[i] + num[j] + num[k];
            if ( sum < target) {
                if(target - sum < minv){
                    minv = target - sum;
                    res = sum;
                }
                j++;
            }
            else if ( sum > target) {
                if(sum - target < minv){
                    minv = sum - target;
                    res = sum;
                }
                k--;
            }
            else {
                minv = 0;
                res = sum;
                flag = 1;
                break;
            }
        }
        if(flag)break;
    }
    return res;
    }
};

No comments:

Post a Comment