思路

参考算法笔记

  1. 枚举左端点，再找到第一个值为sum[i-1]+m的——这一步必须要用二分查找，不然会超时几个测试点
  2. 如果不存在，由于二分查找的结果是第一个大于等于m的值，因此结果比大于等于m，不等于m的话那么大于m，把这个值求出来
  3. 遍历一遍数组，一边遍历一边找符合条件的值

代码

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  6. const int N = 100010;
  8. vector<int> sum(N);
  9. int n, m,nearM = 1000000000;
  11. int upper_bound(int L, int R, int x){
  12.     int left = L, right = R, mid;
  13.     while(left < right){
  14.         mid = left + (right - left)/2;
  15.         if(sum[mid]<=x) left = mid+1;
  16.         else right = mid;
  17.     }
  18.     return left;
  19. }
  21. int main(){
  22.     scanf("%d%d",&n,&m);
  23.     sum[0] = 0;
  24.     for(int i = 1; i <= n; i++){
  25.         scanf("%d",&sum[i]);
  26.         sum[i] += sum[i-1];
  27.     }
  28.     for(int i = 1; i <= n; i++){
  29.         int j = upper_bound(i, n + 1, sum[i-1] + m);
  30.         if(sum[j-1] - sum[i-1]==m){//这里j要-1
  31.             nearM = m;
  32.             break;
  33.         } else if(j <= n&&sum[j] - sum[i - 1] < nearM){//这个一定是大于m的
  34.             nearM = sum[j] - sum[i - 1];
  35.         }
  36.     }
  37.     for(int i = 1; i <= n; i++){
  38.         int j = upper_bound(i, n + 1, sum[i - 1] + nearM);
  39.         if(sum[j - 1] - sum[i - 1] == nearM){
  40.             printf("%d-%d\n",i,j-1);
  41.         }
  42.     }
  43.     return 0;
  44. }

自己写的复杂度是O(n^2)级的，有三个测试点超时了

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  6. int main(){
  7.     int n, m;
  8.     scanf("%d%d", &n, &m);
  9.     vector<int> input(n+1),sum(n+1);
  10.     vector<int> left, right;
  11.     sum[0] = 0, input[0] = 0;
  12.     for(int i = 1; i <= n; i++){
  13.         scanf("%d", &input[i]);
  14.         sum[i] = sum[i-1] + input[i];
  15.     }
  16.     for(int i = 1; i<= n; i++){
  17.         for(int j = i; j <= n; j++){
  18.             if(sum[j]-sum[i-1]==m){//第i个到第j个的和
  19.                 left.push_back(i);
  20.                 right.push_back(j);
  21.             }
  22.         }
  23.     }
  24.     int len = left.size();
  25.     if(len == 0){//没有数字加入,找第一个大于m的和
  26.         int temp = m;
  27.         m = 1000000000;
  28.         for(int i = 1; i<= n; i++){
  29.             for(int j = i; j <= n; j++){
  30.                 if(sum[j]-sum[i-1]<m&&sum[j]-sum[i-1]>temp){//第i个到第j个的和
  31.                     m = sum[j]-sum[i-1];
  32.                     break;
  33.                 }
  34.             }
  35.         }
  36.         //再找一次
  37.         for(int i = 1; i<= n; i++){
  38.             for(int j = i; j <= n; j++){
  39.                 if(sum[j]-sum[i-1]==m){//第i个到第j个的和
  40.                     left.push_back(i);
  41.                     right.push_back(j);
  42.                 }
  43.             }
  44.         }
  45.     }
  46.     len = left.size();
  47.     for(int i = 0; i < len; i++){
  48.         printf("%d-%d\n",left[i],right[i]);
  49.     }
  50. }