• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

每日leetcode–3Sum

leetcode admin 4年前 (2016-05-07) 1961次浏览 0个评论 扫描二维码

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;
			}


		}

	}


};

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明每日 leetcode–3Sum
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!