LeetCode 15 3Sum [sort]

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;
    }
};