LeetCode: 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.

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

---

We can use the same idea as the previous problem. Sort the list first and then try every triple.

C++ Code:

/*
 * func: three_sum_closest
 * goal: to find three numbers in a list whose sum is closest to the
   given target
 * @param num: vector of numbers
 * @param target: the given target value
 * return: the closest sum
 */
/*
 * sort first and try every combination
 * complexity: time O(n^2), space O(1)
 */
int threeSumClosest(vector<int> num, int target) {
    //If there are less than 2 numbers, return target
    if(num.size() <= 2){
        return target;
    }
    
    //Sort the list first
    sort(num.begin(), num.end());
    //variable for current max difference
    int max_diff = numeric_limits<int>::max();
    int ret = numeric_limits<int>::max();
    
    for(int i = 0; i < num.size()-2; ++i){
        //Avoid duplicate cases
        if(i > 0 && num[i] == num[i-1]){
            continue;
        }
        //Use two iters to find b and c which sum up tp -a
        int left = i+1, right = static_cast<int>(num.size())-1;
        while(left < right){
            int sum = num[i] + num[left] + num[right];
            if(abs(sum-target) < max_diff){
                max_diff = abs(sum-target);
                ret = sum;
            }
            //If sum is larger than target, we can move right one left to make
            //the sum smaller
            if(sum > target){
                --right;
            }else if(sum == target){
                return sum;
            }else{
                ++left;
            }
        }
    }
    return ret;
}

Python Code:

# func: find three numbers in a list whose sum is closest to the given target
# @param num: input number list
# @param target: target number
# @return: the closest sum
# complexity: time O(n^2), space O(1)
def three_sum_closest(num, target):
    if len(num) <= 2:
        return target
    else:
        #Sort the num list first
        num.sort()

        max = pow(2, 31)
        #Iterate from the first
        for i in xrange(0, len(num)-2):
            #Avoid some duplicate cases
            if i > 0 and num[i] == num[i-1]:
                continue
            else:
                #Find from the remaining numbers
                left = i+1
                right = len(num)-1
                while left < right:
                    sum = num[i] + num[left] + num[right]
                    if abs(sum - target) < max:
                        #Update result
                        result = sum
                        max = abs(sum - target)

                    #Choose how to move
                    if sum < target:
                        left += 1
                    elif sum == target:
                        #This is the best case
                        return sum
                    else:
                        right -= 1
        return result