3sum 4sum

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