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

• The idea with this one follows the same strategy as 15 3Sum (explanation is in there). The only difference now is that we are iterating towards a target value. Because we're dealing with how close the values are - the difference between the sum and the target value will give us the solution.

• So to do this, I've maintained the minimum difference using a priority queue that pairs with the actual sum. Then I just return the top of the queue.

  • But I could have just as easily maintained the minimum within the algorithm in O(1) and O(1) space using a simple check.

typedef pair<int, int> P;
struct Order {
    bool operator()(P const& a, P const& b) const {
        return a.first > b.first;
        //return a.second < b.second || a.second == b.second && a.first < b.first;
    }
};

int threeSumClosest(vector<int>& nums, int target) {
    if (nums.size() < 3) return 0;

    priority_queue< P, vector<P>, Order> pq;
    sort(nums.begin(), nums.end());

    int cur_sum;
    int main, iter, max;

    for (int main = 1; main <= nums.size(); main++) {

        iter = main + 1;
        max = nums.size() - 1;

        while (max >= iter) {
            //cout << nums.at(main - 1) << " " << nums.at(iter - 1) << " " << nums.at(max) << endl;
            cur_sum = nums.at(main - 1) + nums.at(iter - 1) + nums.at(max);

            // as close as you can get
            if (cur_sum == target)
                return cur_sum;

            else if (cur_sum < target)
                iter++;

            else  // cur_sum > target 
                max--;

            pq.push(make_pair(abs(cur_sum - target), cur_sum));
        }
    }
    return pq.top().second;
}



int main() {
    vector<int> nums = { 1,2,4,8,16,32,64,128 };
    cout << threeSumClosest(nums, 82) << endl;
    pause();

    nums = { -10, 3, 3, -90, 100, 3, 4, 5 };
    cout << threeSumClosest(nums, 1) << endl;
    pause();
}