LeetCode 15 3Sum [sort] <c++>

给出一个一维数组，找出其中所有和为零的三元组（元素集相同的视作同一个三元组）的集合。

C++

先自己写了一发，虽然过了，但跑了308 ms...

我的做法是先排序，扫一遍，处理出unorder_map<0-a[i],i>的hash表。再\(O(n^2)\)枚举前两个元素，查表直接知道第三个元素的位置，然后将三元组加入到答案集合中，通过枚举时添加的限制条件规避重复元素。

复杂度\(O(n^2)\)，由于使用了hash表，常数较大。

class Solution {

public:

    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {

        std::vector<std::vector<int> > res;

        if(nums.size()<3) return res;

        std::sort(nums.begin(),nums.end());

        const int target = 0;

        std::unordered_map<int,int> ump;

        for(auto i=nums.begin();i!=nums.end();i++)

            ump[target-*i] = std::distance(nums.begin(),i)+1;

        for(auto i=nums.begin();i<nums.end();i++){

            if(i>nums.begin() && *i == *(i-1)) continue;

            for(auto j=i+1;j<nums.end();j++){

                if((j>i+1 && *j== *(j-1))|| ump[*i+*j]-1<=std::distance(nums.begin(),j))continue;

                res.push_back({*i,*j,*(nums.begin()+ump[*i+*j]-1)});

            }

        }

        return res;

    }

};

学习一发没有常数的\(O(n^2)\)，只用了64 ms

排序后，枚举第一个元素，左右指针夹逼（根据枚举元素+左指针元素+右指针元素与0的大小关系，判断移动哪一个指针，移动方向一定是使左右指针所夹范围更小的）

class Solution {

public:

    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {

        std::vector<std::vector<int> > res;

        if(nums.size()<3) return res;

        std::sort(nums.begin(),nums.end()); // 先排序

        const int target = 0;

        auto last = nums.end();

        for(auto i = nums.begin();i<last-2;i++){

            auto j = i+1; // 左指针初始化

            if(i>nums.begin()&&*i == *(i-1)) continue; // 避免枚举重复元素

            auto k = last - 1; // 右指针初始化

            while (j < k){

                if(*i+*j+*k<target){ // 左指针右移，使和变大

                    j++;

                    while (*j==*(j-1)) j++; // 跳过重复元素

                }

                else if(*i+*j+*k>target){ // 右指针左移，使和变小

                    k--;

                    while (*k==*(k+1)) k--; // 跳过重复元素

                }

                else{ // 加入答案集合

                    res.push_back({*i,*j,*k});

                    j++;

                    k--;

                    while (*j==*(j-1) && *k==*(k+1) && j<k) j++; // 跳过重复元素

                }

            }

        }

        return res;

    }

};