15. 3Sum

题意：给一堆数，找和为0的三个数，把所有可能情况都返回，但没有重复。

思路

就是先把三个数的和为0转化成两个数的和为第一个数的相反数。先给数排序，按顺序选第一个数，然后后面按两数和来算。
说几个注意的地方：
①每次选了第一个数后做个判断，如果第一个数是正数，就可以直接break然后返回res了，因为第一个数是正数 那么后面肯定都是正数。注意，如果不加这步速度是排在25%，加了这步就是99.7%。

if (nums[a] > 0)
		    break;

②题目要求没有重复情况，所以要跳过重复

	while (b < c && nums[b] == nums[b - 1])
                        ++b;
    while (b < c && nums[c] == nums[c + 1])
                        --c; 
                       

	while (a < sz - 2 && nums[a + 1] == nums[a])
                ++a;

ok，上代码：

    vector<vector<int>> threeSum(vector<int>& nums) {
        int a=0 , b , sz = nums.size(), c;
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        while (a < sz - 2) {
        	if (nums[a] > 0)
			    break;
            b = a + 1;
            c = sz - 1;
            while (b < c)
                if (nums[b] + nums[c] == 0 - nums[a]) {
                    res.push_back({ nums[a],nums[b++],nums[c--]});
                    while (b < c && nums[b] == nums[b - 1])
                        ++b;
                    while (b < c && nums[c] == nums[c + 1])
                        --c; 
                }	
                else if ( nums[b] + nums[c] > 0 - nums[a] )
                    --c;
                else
                    ++b;
            while (a < sz - 2 && nums[a + 1] == nums[a])
                ++a;
            ++a;
        }
        return res;
    }