3 Sum Closest@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

3Sum Closest

 

AC Rate: 545/1778

My Submissions

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

和3 sum几乎一样，用一个variable来record target - sum的绝对值，一直变动。但要注意的是：一旦遇到sum == target的，要break!

	class Solution {
	public:
	int threeSumClosest(vector<int> &num, int target) {
	// Note: The Solution object is instantiated only once and is reused by each test case.
	if(num.empty()) return 0;
	sort(num.begin(), num.end());
	int min= INT_MAX;
	int record;
	for(int i=0; i<num.size(); i++)
	{
	int tmp = target - num[i];
	int start = i+1, end = num.size()-1;
	while(start<end)
	{
	int sum = num[start]+num[end]+num[i];
	if(sum==target)
	{
	min = 0;
	record = sum;
	break;
	}
	else if(sum > target)
	{
	if(abs(target-sum)<min)
	{
	min = abs(target-sum);
	record = sum;
	}
	end--;
	}
	else if(sum < target)
	{
	if(abs(target-sum)<min)
	{
	min = abs(target-sum);
	record = sum;
	}
	start++;
	}
	while(i<num.size()-1&&num[i]==num[i+1]) i++;
	}
	}
	return record;
	}
	};

view raw 3 Sum Closest hosted with ❤ by GitHub