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
    
     
      > threeSum(std::vector
      
       & nums) {        std::vector
       
        
          > res;        if(nums.size()<3) return res;        std::sort(nums.begin(),nums.end());        const int target = 0;        std::unordered_map
         
           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.begin() && *i == *(i-1)) continue; for(auto j=i+1;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
    
     
      > threeSum(std::vector
      
       & nums) {        std::vector
       
        
          > 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
         
          nums.begin()&&*i == *(i-1)) continue; // 避免枚举重复元素 auto k = last - 1; // 右指针初始化 while (j < k){ 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