3Sum.txt

problem：
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)
--------------------------------------------------------------------------------------
solution：
//思路，两重循环取出a, b，再用二分查找找出满足条件a + b + c = 0的c。因为要用二分，所以刚开始需要排序
//需要注意结果的去重。用到vector的unique和erase函数。
//unique函数只能检测相邻的重复元素，因此要使unique奏效，需要先对vector里的元素排序；此外unique函数并不是把重复元素之间删除
//而是把重复元素放到容器的后面，而它本身返回一个迭代器，指向重复元素的开始部分，因此要真正删除需要配合erase函数使用。
//sort(n.begin(), n.end());
//n.erase(unique(n.begin(), n.end()), n.end());

vector<vector<int> > threeSum(vector<int> &num) 
{
  vector<vector<int>> ret;
	if(num.size() < 3)
		return ret;
	sort(num.begin(), num.end());
	vector<int> tmp;
	for(int i = 0; i < num.size() - 2; i++)
	{
		int a = num[i];
		for(int j = i + 1; j < num.size() - 1; j++)
		{
			int b = num[j];
			int target = -a - b;
			int l = j + 1;
			int r = num.size() - 1;
			while(l <= r)
			{
				int mid = (l +r) / 2;
				if(num[mid] == target)
				{
					tmp.clear();
					tmp.push_back(a);
					tmp.push_back(b);
					tmp.push_back(target);
					ret.push_back(tmp);
					break;
				}
				else if(num[mid] > target)
					r = mid - 1;
				else
					l = mid + 1;
			}
		}
	}
	sort(ret.begin(), ret.end());
	ret.erase(unique(ret.begin(), ret.end()), ret.end());
	return ret;
}

////////////////
思路二：如同2sum一样的思路，一层循环遍历一个数，然后前后两个指针相对而行
重点！！两个地方都对有重复元素时进行优化
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ret;
        if(num.size() == 0)
            return ret;
        vector<int> sub;
        sort(num.begin(), num.end());
        for(int i = 0; i < num.size() - 1; ++i)
        {
            int p = i + 1;
            int q = num.size() - 1;
            int a = num[i];
            while(p < q)
            {
                int b = num[p];
                int c = num[q];
                if(a + b + c == 0)
                    {
                        sub.clear();
                        sub.push_back(a);
                        sub.push_back(b);
                        sub.push_back(c);
                        ret.push_back(sub);
                        p++;
                        q--;
                        while(p < q && num[p] == num[p - 1])p++;  //a + b + c = 0中对b重复时的优化
                        while(p < q && num[q] == num[q + 1])q--; //a + b + c = 0中对c重复时的优化
                    }
                else if(a + b + c > 0)
                    q--;
                else
                    p++;
            }
            if(i < num.size() - 1) //a + b + c = 0中对a重复时的优化
            {
                while(num[i + 1] == num[i])i++;
            }
        }
        return ret;
    }
};