共计 1086 个字符，预计需要花费 3 分钟才能阅读完成。
这道题可以利用二分来做，其实个人觉得动态规划也可以；利用二分的前提条件就是该序列是一个不下降序列；所以我们可以先构建一个 sum 数组，存放 1 - i 的和值；当然题目中要计算 i - j 子序列的值，其实这个可以利用 sum 数组来计算，该子序列的和就是 sum[j]-sum[i]；所以我们就相当于对 sum 和二分序列寻找 sum[i]+x，其中，x 为题目前提给出的和值；
对于二分算法，使用大于 x 和大于等于 x 的两种都可以，示例给出的是大于 x，然后通过判断 j - 1 位是不是可以使得子序列和等于 x; 个人觉得麻烦，还是使用大于等于 x 较为简单；
其实这道题的关键还是怎么转化数组使得其能够用二分法进行解决；还有一个问题，如果不仅仅包括 0 - n 位，会出现第 n 位元素无法进行判断的情况，所以包括的序列一定要为 1~n+1，这样就可以有效的使得随后一位进行计算，使得小于 x 的时候出现第 n + 1 位无效位，从而根据位数是否无效来剔除这种意外之外的情况；
算法实现如下，使用的是大于等于 x：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
const int maxn=100010;
int a[maxn],sum[maxn];
int n,m,ns=100000010;
int binarySearch(int l,int r,int x){
while(l<r){
int mid=(l+r)/2;
if(sum[mid]>=x){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
int main(){
scanf(“%d”,&n);
scanf(“%d”,&m);
for(int i=1;i<=n;i++){
scanf(“%d”,&a[i]);
}
sum[0]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}
// 此时 sum 递增；
for(int i=1;i<=n;i++){
int j=binarySearch(i,n+1,sum[i-1]+m);
if(sum[j]-sum[i-1]==m){
// 如果存在和 s 相等的数；
ns=m;
break;
}else if(j<=n&&sum[j]-sum[i-1]<ns){
ns=sum[j]-sum[i-1];
}
}
for(int i=1;i<=n;i++){
int j=binarySearch(i,n+1,sum[i-1]+ns);
if(sum[j]-sum[i-1]==ns){
printf(“%d-%d\n”,i,j);
}
}
system(“pause”);
return 0;
}
