LeetCode Q16: 3Sum Cloest

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

I first come up with a wrong solution which seems to be  very reasonable and actually similar to the final correct one. The idea in this wrong solution works by using two pointers pointing to the start and end of the sorted array. In every iteration, search the best result inbetween two pointers. Adjust (increase low point or decrease high pointer) the pointers according to the best result of current iteration. Actually so far I still can not figure out why this solution is wrong. Following is the code for this wrong soluton

• Wrong solution

	#include <stdlib.h>
	#include <stdio.h>
	#include <string>
	#include <vector>
	#include <limits.h>
	using namespace std;
	void sortNums(vector<int>& nums)
	{
	int minv=nums[0];
	int maxv=nums[0];
	for(int i=0; i<nums.size(); ++i)
	{
	if(nums[i]<minv) minv=nums[i];
	if(nums[i]>maxv) maxv=nums[i];
	}
	int len=maxv-minv+1;
	vector<int> bucket(len, 0);
	for(int i=0; i<nums.size(); ++i)
	{
	bucket[nums[i]-minv]++;
	}
	nums.clear();
	for(int i=0; i<bucket.size(); ++i)
	{
	if(bucket[i]==0) continue;
	for(int j=0; j<bucket[i]; ++j)
	{
	nums.push_back(minv+i);
	}
	}
	}
	int threeSumClosest(vector<int>& nums, int target)
	{
	sortNums(nums);
	for(int i=0; i<nums.size(); ++i){
	printf("%d\n", nums[i]);
	}
	int s=0;
	int e=nums.size()-1;
	int cloest=INT_MAX;
	int result=0;
	while(s<=e-2)
	{
	int v0=nums[s];
	int v2=nums[e];
	for(int i=s+1; i<e; i++)
	{
	int v1=nums[i];
	int tmpr=v0+v1+v2;
	if(abs(tmpr-target)<cloest)
	{
	cloest=abs(tmpr-target);
	result=tmpr;
	}
	}
	if(result<target)
	s++;
	if(result>target)
	e--;
	if(result==target)
	return result;
	}
	return result;
	}
	int main(int argc, char** argv)
	{
	int a[]= {4,0,5,-5,3,3,0,-4,-5};
	int target = -2;
	vector<int> nums(a, a+sizeof(a)/sizeof(int));
	int r=threeSumClosest(nums, target);
	int zx=0;
	}

view raw Q16Wrongsolution.cpp hosted with ❤ by GitHub

In correct solution, the idea is very similar to the one I described above. But difference is that, in this solution, in i=th iteration we keep the first pointer fixed at i-th element, and start a same searching process using two pointers as I described in the wrong solution. Following is the code for this correct solution 

• Correct solution

	class Solution {
	public:
	int threeSumClosest(vector<int>& nums, int target) {
	long res=INT_MAX;
	sort(nums.begin(), nums.end());
	for(int i=0; i<nums.size()-2; i++){
	int p0 = i+1, p1 = nums.size()-1;
	while(p0<p1){
	int sum = nums[i]+nums[p0]+nums[p1];
	if(abs(sum-target)<abs(res-target))
	res = sum;
	if(sum<target)
	p0++;
	else
	p1--;
	}
	}
	return res;
	}
	};

view raw Q16CorrectSolution.cpp hosted with ❤ by GitHub