3Sum Closest Problem Analysis

Overview

In this post, we discuss a problem called “3Sum Closest problem” which is very similar to 3sum problem discussed in our previous post: “3Sum Problem Analysis: Handling Duplicates Without Using Set“. The source code turns out to be simplified in less than 20 lines and sorting method again is adopted.

3Sum Closest Problem

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

3Sum Closest Solution Analysis:

The idea is very simple and if you have read the 3sum problem post, the solution would be quite straightforward and it is simpler here because exactly one solution is assumed. The basic idea is as follows:

Basically we need to minimize the absolute value of (target – (A[i] + A[j] + A[k]). We follow exactly the same procedure as in 3sum problem by first sorting the whole array and (copyright @sigmainfy) linear scan the rest of the array to find two sum.

If the sum of the triplet is greater than the target, it is obvious that we need to reduce the sum, so set k = k – 1. Similarly if sum of the triplet is less than the target, then we set j = j + 1, at the same time if we got a sum closer to the target, we keep record of it. The accepted source code by leetcode OJ is as follows:

class Solution {
public:
	int threeSumClosest(vector<int> &num, int target) {
		int diff = INT_MAX, ret = 0;
		sort(num.begin(), num.end());
		int lastIndex = num.size() - 2, j = 0, k = num.size() - 1;
		for (int i = 0; i < lastIndex; ++i) {
			j = i + 1, k = lastIndex + 1;
			while (j < k) {
				int threeSum = num[i] + num[j] + num[k];
				int tmpdiff = threeSum - target;
				if (0 == tmpdiff) return target;
				if (abs(tmpdiff) < diff) diff = abs(tmpdiff), ret = threeSum;
				tmpdiff < 0 ? ++j : --k;
			}
		}
		return ret;
	}
};

Note we do not have to know the exact triplet with the closest sum to the target, this would make the code shorter.

Conclusion:

To summarize, 3sum closest problem is discussed in this post and a copy of compact code with less than 20 lines is given, the idea here is the same as in original 3sum problem. One could treat this (copyright @sigmainfy) problem as a simple extended exercise for the 3sum problem.

Written on September 22, 2014