Finding sum of triplets that is closest to a given number (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.
INPUT: S = {-1, 2, 1, -4} and target = 1
OUPUT: 2 since the sum that is closest to the target is 2 (-1 + 2 + 1 = 2).

Thoughts:
The approach should be similar to the problem 3sum. There are only two things we need to add:

  1. If we have found a sum that is exactly the target, we can just return it since you cannot find a even closer sum that the target itself.
  2. Along the search, we keep a record of current closest sum and the corresponding difference between it and the target. We then updae those two variables as we go.

Code (Java):

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int sol = target;
        int min_diff = Integer.MAX_VALUE;
        Arrays.sort(num);
        for(int i = 0; i < num.length; ++i) {
            int low = i + 1;
            int high = num.length - 1;
            while(low < high) {
                int sum = num[i] + num[low] + num[high];
                if(sum == target)
                    return sum;
                else if(sum > target) {
                    int diff = Math.abs(sum - target);
                    if(diff < min_diff) {
                        min_diff = diff;
                        sol = sum;
                    }
                    high--;
                } else { // sum < target
                    int diff = Math.abs(sum - target);
                    if(diff < min_diff) {
                        min_diff = diff;
                        sol = sum;
                    }
                    low++;
                }
            }
        }
        return sol;
    }
}

Code (C++):

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        int sol = target;
        int min_diff = INT_MAX;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size(); ++i) {
            int low = i + 1;
            int high = num.size() - 1;
            while(low < high) {
                int sum = num[i] + num[low] + num[high];
                if(sum == target)
                    return sum;
                else if(sum > target) {
                    int diff = abs(sum - target);
                    if(diff < min_diff) {
                        min_diff = diff;
                        sol = sum;
                    }
                    high--;
                } else { // sum < target
                    int diff = abs(sum - target);
                    if(diff < min_diff) {
                        min_diff = diff;
                        sol = sum;
                    }
                    low++;
                }
            }
        }
        return sol;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: