[LeetCode]3Sum Smaller

这道题仍然是延续3Sum的解法，reduce成2Sum之后，双指针lo和hi，对于每一个lo，找到满足条件最大的hi，之后lo移去下一个位置。因为hi是单调递减的，所以这个过程O(N)可以完成，总的时间复杂度就是O(N^2)，常数空间，代码如下：

	class Solution {
	public:
	int threeSumSmaller(vector<int>& nums, int target) {
	int len = nums.size(), res = 0;
	if (len < 3)return 0;
	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)
	--hi;
	else
	{
	res += hi - lo;
	++lo;
	}
	}
	}
	return res;
	}
	};

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