[LeetCode]3Sum Smaller

这道题和3Sum是类似的，reduce成2Sum问题。只是我们不能用hashmap解决，但是找closet我们仍然是可以用two pointer的。时间复杂度O(N^2)，常数空间。代码如下:

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

view raw 3Sum Closest.cpp hosted with ❤ by GitHub