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的解法以后补。

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 16时07分00秒
File Name :15.cpp
************************************************ */
class Solution {
public:
    set<vector<int> >se;
    vector<vector<int> >res;
    vector<vector<int>> threeSum(vector<int>& nums) {
	sort(nums.begin(),nums.end());
	int n = nums.size();
	for ( int i = 0 ; i <=n-3 ; i++)
	{
	    int head = i+1;
	    int tail = n-1;
	    int tar = -nums[i];
	    while (head<tail)
	    {
		if (nums[head]+nums[tail]==tar)
		{
		    vector<int>tmp;
		    tmp.push_back(nums[i]);
		    tmp.push_back(nums[head]);
		    tmp.push_back(nums[tail]);
		    se.insert(tmp);
		    head++;
		    tail--;
		}
		else if (nums[head]+nums[tail]<tar) head++;
		else tail--;
	    }
	}
	for ( auto &it : se)
	    res.push_back(it);
	return res;
    }
};