15. 三数之和*

[MyLinChi]

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

链接：https://leetcode-cn.com/problems/3sum

方案

分两步，第一步排序，第二步查找。通过固定a，b+c为一个常数且在a的右边，用快速排序的思想进行查找。
坑一：vector的size函数返回unsigned型数据，做减法时可能发生溢出。
坑二：为了避免产生重复的三元组，重复的a要略去，当找到一个相同结果时重复的b要略去，这两种情况都要考虑数组溢出的可能。

using namespace std;
class Solution {
public:
	void fastsort(vector<int>& nums,int a,int b){
		if (a>=b||nums.size()<=1)return;
		int i,j,tmp = nums[a];
		for (i = a, j = b; i < j;){
			while(i<j && nums[j] >= tmp)j--;
			nums[i] = nums[j];
			while (i < j&&nums[i] <= tmp)i++;
			nums[j] = nums[i];
		}
		nums[j] = tmp;
		fastsort(nums,a,j-1);
		fastsort(nums,j+1, b);
	}
	vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> res = {};
		fastsort(nums,0,nums.size()-1);
		for (int a = 0; a+2 < nums.size();){
			for (int b = a+1, c = nums.size() - 1; b < c;){
				if ((nums[a] + nums[b] + nums[c]) < 0)b++;
				else if ((nums[a] + nums[b] + nums[c])>0)c--;
				else {
					res.push_back({nums[a],nums[b],nums[c]});
					do{
						b++;
					} while (b<c && nums[b] == nums[b - 1]);
					c--;
				}
			}
			do{
				a++;
			} while ((a+2)<nums.size()&&nums[a]==nums[a-1]);
		}
		return res;
	}
};

2020/9/1
排序后固定左边的一种值转化为twoSum问题，{a,b,c}中略过重复的a,b。

class Solution {
private:
    vector<vector<int>> res;
    void twoSum(vector<int>& nums,int s,int sum){
        int left = s;
        int right = nums.size()-1;
        for(;left<right;){
            if(left>s && nums[left]==nums[left-1]){
                ++left;
                continue;
            }
            int t = nums[left]+nums[right];
            if(t == sum){
                res.push_back({-sum,nums[left],nums[right]});
                ++left;
                --right;
            }else if(t > sum){
                --right;
            }else{
                ++left;
            }
        }
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        for(int i=0;i<len-2;++i){
            if(i==0||nums[i]!=nums[i-1])
            twoSum(nums,i+1,-nums[i]);
        }
        return res;
    }
};