每日leetcode–3Sum

共计 1086 个字符，预计需要花费 3 分钟才能阅读完成。

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

华丽的分割线，刷OJ真的是磨练一个人的事情。。。。。。。。。。。。。。

class Solution {
public:
	vector<vector> threeSum(vector& nums) {

		vector<vector>result;
		if (nums.size() < 3)
		return vector<vector>{};

		sort(nums.begin(), nums.end());

		//去重复
		for (int i = 0; i < nums.size() - 2; i++) 
               {            
                if(i > 0 && nums[i] == nums[i-1])continue;//重复的元素不用计算
                int target2 = 0 - nums[i];
                 twosum(i+1,  target2, nums,result);
		}
		return result;
	}
	void twosum(int start, int target, vector& nums, vector<vector>&result)
	{
		int first = start;
		int second = nums.size()-1;

		while (first < second)
		{
			int k = nums[first] + nums[second];

			if (k < target) 			
                         { 			
	                   first++; 		
	                 } else if (k > target)
			{
				second--;

			}
			else
			{
				result.push_back(vector{nums[start-1], nums[first], nums[second]});

				//为了防止出现重复的二元组，使结果等于target
				int tmp = first + 1;
				while (tmp< second && nums[tmp] == nums[first]) 				
                                { 					
                                      tmp++; 				
                                 } 				
                                first = tmp; 				
                                tmp = second - 1; 				
                                while (tmp > first && nums[tmp] == nums[second])
				{
					tmp--;
				}
				second = tmp;
			}


		}

	}


};