3sum 4sum

作者: rsliumin1994 | 来源:发表于2017-03-27 10:49 被阅读0次
Paste_Image.png

思路:

  1. 对数据进行排序
    2)为了得到非重复的三元组 不断移动哨兵位置
    时间复杂度为O(n*n)
    对于4 sum问题 其时间复杂度为O(n^3)
vector<vector<int>> threeSum(vector<int>& nums) {
      
      vector<vector<int>> res;
      if(nums.size()<3)
      return res;
      sort(nums.begin(),nums.end());
      int left,right;
      for(int i=0;i<nums.size()-2;i++)
      {
          left=i+1;right=nums.size()-1;
          int target=0-nums[i]; 
          while(left<right)
          {
              int temp=nums[left]+nums[right];
              if(temp==target)
              {
                  vector<int> hh={nums[i],nums[left],nums[right]};
                  //sort(hh.begin(),hh.end());
                  res.push_back(hh);
                  while(nums[left]==hh[1]&&left<right)
                  left++;
                  while(nums[left]==hh[1]&&left<right)
                  right--;
                  continue;
              }
              if(temp>target)
              {
                  right--;
                  continue;
              }
              if(temp<target)
              {
                  left++;
                  continue;
              }
          }
          //理解为什么要这样去除重复数据
          while (i + 1 < nums.size() && nums[i + 1] == nums[i]) 
            i++;
      }
    
      return res;
    }
Paste_Image.png

思路:
1)将数据分为前后两部分
2)C、D数组数据相加后添加到unordered_map中,map键为和,值为个数
时间复杂度:O(n*n)

 int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int N=A.size();
        vector<int> dt;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        dt.push_back(A[i]+B[j]);
        //将4个数组分为两部分,dt存储前一部分
        //kk 存储寻找的数据 使用键作为数据 值作为数据的个数
        unordered_map<int,int> kk;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        kk[C[i]+D[j]]++;
        int res=0;
        for(int i=0;i<dt.size();i++)
        {
            if(kk.find(0-dt[i])!=kk.end())
            res+=kk.find(0-dt[i])->second;
        }
        return res;
    }

相关文章

网友评论

      本文标题:3sum 4sum

      本文链接:https://www.haomeiwen.com/subject/gqolottx.html