学步园

typedef tuple<int, int, int> ABC; //存放a,b,c三元组
//返回所有满足条件的(a,b,c)三元组
vector<ABC> threeSumZero(vector<int> &arr) {
	vector<ABC> ret;
	if ( arr.size()<3 )
		return ret;

	sort(arr.begin(),arr.end());
	for(int t=arr.size()-1;t>=2;)
	{
		int target=0-arr[t];
		int l=0,r=t-1;
		while(l<r)
		{
			int sum=arr[l]+arr[r];
			if ( sum == target )
			{
				ret.push_back(ABC(arr[l],arr[r],arr[t]));
				int tmp=arr[l];
				while(arr[l]==tmp&&l<r )
					l++;
			}
			else if ( sum<target)
				l++;
			else
				r--;
		}
		int tmp=arr[t];
		while(t>=2&&arr[t]==tmp)
			t--;
	}
	return ret;
}