leetcode 15. 3Sum (k-sum问题,two pointer)

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: The solution set must not contain duplicate triplets.

思路:排序O(nlgn),然后枚举一个元素O(n),对于每个元素,在剩下的区间中 two pointer O(n)

整体复杂度 O(n^2)。

hash的解法以后补。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月13日 星期四 16时07分00秒
 4File Name :15.cpp
 5************************************************ */
 6class Solution {
 7public:
 8    set<vector<int> >se;
 9    vector<vector<int> >res;
10    vector<vector<int>> threeSum(vector<int>& nums) {
11	sort(nums.begin(),nums.end());
12	int n = nums.size();
13	for ( int i = 0 ; i <=n-3 ; i++)
14	{
15	    int head = i+1;
16	    int tail = n-1;
17	    int tar = -nums[i];
18	    while (head<tail)
19	    {
20		if (nums[head]+nums[tail]==tar)
21		{
22		    vector<int>tmp;
23		    tmp.push_back(nums[i]);
24		    tmp.push_back(nums[head]);
25		    tmp.push_back(nums[tail]);
26		    se.insert(tmp);
27		    head++;
28		    tail--;
29		}
30		else if (nums[head]+nums[tail]<tar) head++;
31		else tail--;
32	    }
33	}
34	for ( auto &it : se)
35	    res.push_back(it);
36	return res;
37    }
38};