带有总和CPP的子阵列

Question

1. IAM由于复杂性O（n logn）而导致误差为TLE，而给定的QS需要在O（n）中求解。
2. 需要找到m.find（）方法的替代方案，因为它正在采用O（logN）复杂性，并且总复杂性变为O（nlog n）。

    vector<int> subarraySum(int a[], int n, long long s)
    {
       vector<int> result;
       map<int,int>m;
       map<int,int>::iterator it;
       int b[n];
       b[0]=a[0];
       for(int i=1;i<n;i++){
           b[i]=b[i-1]+a[i];
        }
          
        for(int i=0;i<n;i++){
            m.insert({ b[i],i });
        }
        for(it=m.begin();it!=m.end();it++){
          if((it->first-s)==0){
            result.push_back(1);
            result.push_back((it->second)+1);
            break;
            }
            if(m.find(it->first-s)!=m.end()){
               result.push_back(m[it->first-s]+2);
               result.push_back((it->second)+1);
                break;
             }
        }
           if(result.empty())
            result.push_back(-1);
            return result;
    }

Answer 1

您应该学习滑动窗口算法： httpps://en.wikipedia.org/wikipedia.org/wiki/wiki/wiki/streaming_algorith_algorith_algorithm < /a>