法一：暴力$O({n^2})$看脸过

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 int a[50002],sum[50002]; 5 int main(){ 6     int n,k; 7     cin>>n>>k; 8     for(int i=1;i<=n;i++){ cin>>a[i];sum[i]=sum[i-1]+a[i];}  9     bool flag=false;10     for(int i=0;i
     

法二：map优化，存储sum数组的下标，复杂度$O(n\log n)$

 

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 ll a[50002],s[50002]; 5 int main(){ 6     map
      
       m; 7     ll n,k; 8     cin>>n>>k; 9     for(ll i=1;i<=n;i++){ cin>>a[i];s[i]=s[i-1]+a[i];}10     for(ll i=n;i>=1;i--) m[s[i]]=i;11     bool ok=false;12     ll l,r;13     m[0]=0;14     for(ll i=1;i<=n;i++){15         16         if(s[i]-k==0&&!ok) l=1,r=i,ok=true; 17         18         else if(m[s[i]-k]){19             if(m[s[i]-k]+1>i) continue;20             if(!ok) l=m[s[i]-k]+1,r=i,ok=true;21             else{22                 if(m[s[i]-k]+1
      
     

法三：二分复杂度$O(n\log n)$，特别注意二分时的判断条件，很容易出错，idx和sum不可以一起判断，只能判断完sum，再独自判断idx，否则答案会出错

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 struct node{ 5     ll sum,idx; 6 }a[10002]; 7 ll b[10002]; 8 ll n,k; 9 bool cmp(node &a,node &b){10     return (a.sum
      
       
        >1;16         if(a[mid].sum>=p) r=mid;17         else l=mid+1;18     }19     return r;20 } 21 int main(){22     cin>>n>>k;23     for(ll i=1;i<=n;i++){24         cin>>a[i].sum;25         a[i].sum+=a[i-1].sum;26         a[i].idx=i;27         b[i]=a[i].sum;28     }29     bool flag=false;30     sort(a+1,a+n+1,cmp);31     for(ll i=1;i<=n;i++){32         ll p=b[i-1]+k;33         ll idx=erfen(p,i);34         while(a[idx].idx