[leetcode] 16 3Sum Closest(数组)

暴力循环的时间复杂度是O(N^3),肯定是不可取的。我们要充分利用题目中的条件进行分析，如何才能相对高效的比较数组中指定个数元素的和  和target的大小呢？

我们可以先对数组进行排序，如果是计算两个元素的和的话，我们会分别设置头和尾两个指针，向中间靠拢，那么三个的话，我们只需要先对第一个数进行循环取值下标i，剩下的两个指针分别指向i+1和数组的最后一个元素，这样的复杂度是 排序O(nlogn) + 查找O(n^2) = O(n^2)。

注：不要sum>target就 return，也许在下一个循环中还会有合适的。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans,k,sum,j;
		sort(nums.begin(),nums.end());
		int flag=0;
	    for(int i=0;i<nums.size();i++)
	    {
    		j=i+1;
    		k=nums.size()-1;
    		goout=0;
    		while(j<k)
    		{
		    	sum=nums[i]+nums[j]+nums[k];
 	
		    	if(flag==0)
		    	{
	    			ans=sum;
	    			flag=1;
	    		}
	    		
	    		if(abs(sum-target)<abs(ans-target))
	    		ans=sum;
	    		
	    	    if(ans==target)
	    		return ans;
	    		
	    		if(sum<target)
	    		j++;
	    		else 
	    		k--;
		    }
		    
		    
    	}
        loop:
        return ans;
    }
};

[leetcode] 16 3Sum Closest(数组)

原文：http://blog.csdn.net/nk_test/article/details/49721047