leetcode15题解

题目描述

给定一个整数数组 nums，返回所有满足以下条件的三元组 [nums[i], nums[j], nums[k]]：

1. 索引 i、j、k 互不相等，即 i ≠ j、i ≠ k 且 j ≠ k；
2. 三个元素的和为 0，即 nums[i] + nums[j] + nums[k] == 0。

注意，最终返回的解决方案集合中，不得包含重复的三元组。

解题思路

暴力

最朴素的想法一定是暴力解法，但是会超时。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int size=nums.size();
        int sum;
        vector<vector<int>> res;

        sort(nums.begin(),nums.end());
        int lasti=-99999;
        for(int i=0;i<size;i++){
            if(nums[i]>0) break;
            if(nums[i]==lasti) continue;
            lasti=nums[i];
            int lastj=-99999;
            
            for(int j=size-1;j>=i;j--){
                if(nums[j]<0) break;
                if (lastj==nums[j]) continue;
                lastj=nums[j];
                for(int k=i+1;k<j;k++){
                    if (nums[k]+nums[i]+nums[j]==0) 
                    {
                        res.push_back({nums[i],nums[k],nums[j]});
                        break;
                    }
                }
            }
        }
        return res;


    }
};

双指针

• 在最开始考虑双指针的时候，我考虑的是先考虑左右两侧的限界，随后在中间找，三数之和大于零就让右指针向左移，否则左指针向右移，但是会发现这样会漏掉一部分结果，例如10=-5+-5，这样一高两低的办法导致了右指针更快地移走了，忽略掉了这个情况。
• 于是先中间后两边。排序之后，先定义一个变量i，让i遍历所有可能的取值（注意并非所有值）。此时大于零右指针向左，小于零左指针向右即可找到所有解。吗？

  • 实际上并不是这样的，因为i在不同的位置，会有不同的左指针取值可能。i处于某一个同值簇的时候，左指针可以取到和i位置相同的值，带来差异，因此要在发现i与i-1相同时看看是否有这样的右指针找到一个正确的解。 ```c++ class Solution { public: vector<vector> threeSum(vector& nums) { int size=nums.size(); int sum; vector<vector> res;

    sort(nums.begin(),nums.end()); //copy(nums.begin(),nums.end(),ostream_iterator(cout," ")); //cout<<endl; int lasti=INT_MIN; int i=0; while(i<size){ if(i!=size-2&&nums[i]==nums[i+1]){ for(int k=i+2;k<size;k++){ if(nums[i]+nums[i+1]+nums[k]==0){ res.push_back({nums[i],nums[i+1],nums[k]}); //cout<<"a"<<i<<" "<<i+1<<" "<<k<<endl; break; } } } do{ ++i; if(i==size-1) break; }while(nums[i-1]==nums[i]); if(i==size-1) break;

      lasti=nums[i];
      int lp,rp;
    
      lp=0;
      rp=size-1;
      int lastlp=INT_MIN;
      int lastrp=INT_MAX;
      while(lp<i&&i<rp){
          if(nums[lp]+nums[i]+nums[rp]<0){
              lastlp=nums[lp];
              while(lastlp==nums[++lp]&&lp<i&&i<rp)
                  ;
                    
          }
          else if(nums[lp]+nums[i]+nums[rp]>0){
              lastrp=nums[rp];
              while(lastrp==nums[--rp]&&lp<i&&i<rp)
                  ;
    
          }
          else{
              //copy(nums.begin(),nums.end(),ostream_iterator<int>(cout," "));
              //cout<<endl;
              if(!(res.size()>0&&nums[i]==res.back()[1]&&nums[lp]==res.back()[0]))
              {
                  res.push_back({nums[lp],nums[i],nums[rp]});
                  //cout<<lp<<" "<<i<<" "<<rp<<" "<<endl;
              }
              lastlp=nums[lp];
              while(lastlp==nums[++lp]&&lp<i&&i<rp)
                  ;
          }
    
      }   }   return res;
    

  } }; ```