三数之和（C++）

注意：答案中不可以包含重复的三元组。

leetcode链接

示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

示例 2： 输入：nums = [] 输出：[]

示例 3： 输入：nums = [0] 输出：[]

思路：先给数组进行从小到大排序。然后定义三个指针：first，second，third，分别代表三元组的三个下标。
first下标从0开始，到nums.size()-1结束。
second下标从first+1开始，third下标从nums.size()-1开始，second要始终小于third。
如果nums[first]+nums[second]+nums[third]>0，说明三数之和大于0，此时third应该往左走，使三数之和减小。
如果nums[first]+nums[second]+nums[third]<0，说明三数之和小于0，此时second应该往右走，使三数之和增加。直到second和third相遇。
另外，要注意去重。

代码：

class Solution {	//三数之和
public:
	vector> threeSum(vector& nums) {
		vector> result;
		sort(nums.begin(), nums.end());
		if (nums.size() < 3)
			return result;
		for (int first = 0; first < nums.size(); first++) {
			if (nums[first] > 0)
				return result;
			if (first > 0 && nums[first] == nums[first - 1])
				continue;
			int second = first + 1;
			int third = nums.size() - 1;
			while (second < third){
				if (nums[first] + nums[second] + nums[third] > 0) {
					third--;
					while (second < third && nums[third] == nums[third + 1])
						third--;
				}
				else if (nums[first] + nums[second] + nums[third] < 0) {
					second++;
					while (second < third && nums[second] == nums[second - 1])
						second++;
				}
				else {
					result.push_back(vector{nums[first], nums[second], nums[third]});
					while (second < third && nums[third] == nums[third - 1])
						third--;
					while (second < third && nums[second] == nums[second + 1])
						second++;
					second++;
					third--;
				}
			}
		}
		return result;
	}
};