【LeetCode 16】 threeSumClosest

/***********************************LeetCode 16 threeSumClosestGiven 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).************************************//******************************思想：   1.对数组进行快速排序   2.遍历数组     固定一个数num[i]，取start = i+1 end=len-1	 nums[ii] + nums[start] + nums[end]>target  说明三个数和大于目标数  因此 end--;	 nums[ii] + nums[start] + nums[end]<target  说明三个数和小于目标数  因此 start--;   3.在上述过程中，比较sum和diff = abs(nums[ii] + nums[start] + nums[end]-target),记录diff最小的sum   4.遍历完成，sum即是最终的结果时间复杂度：    排序： nlgn	遍历： n^2	最终时间复杂度为 O(n^2)************************************/int threeSumClosest(vector<int>  &nums, int target){	if (nums.size()<3)	{		return 65535;	}	sort(nums.begin(), nums.end());	int diff = 0;	int sum = 0; 	for (int ii = 0; ii < nums.size() - 2; ii++)	{		int start = ii + 1;		int end = nums.size() - 1;				while (start<end)		{			if (abs(nums[ii] + nums[start] + nums[end] - target)<diff)			{				diff = abs(nums[ii] + nums[start] + nums[end] - target);				sum = nums[ii] + nums[start] + nums[end];			}			if (nums[ii] + nums[start] + nums[end] == target)			{				return target;			}			else if (nums[ii] + nums[start] + nums[end] > target)			{				if (abs(nums[ii] + nums[start] + nums[end] - target)<diff)				{					diff = abs(nums[ii] + nums[start] + nums[end] - target);					sum = nums[ii] + nums[start] + nums[end];				} 				end--;			}			else			{				if (abs(nums[ii] + nums[start] + nums[end] - target) < diff)				{					diff = abs(nums[ii] + nums[start] + nums[end] - target);					sum = nums[ii] + nums[start] + nums[end];				} 				start++;			} 		} 	}	return sum;}