本文主要是介绍51nod 和为k的连续区间（map／暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
收藏 
关注 一整数数列a1, a2, ... , an（有正有负），以及另一个整数k，求一个区间[i, j]，(1 <= i <= j <= n)，使得a[i] + ... + a[j] = k。
Input
第1行：2个数N,K。N为数列的长度。K为需要求的和。(2 <= N <= 10000，-10^9 <= K <= 10^9) 第2 - N + 1行：A[i](-10^9 <= A[i] <= 10^9)。
Output
如果没有这样的序列输出No Solution。 输出2个数i, j，分别是区间的起始和结束位置。如果存在多个，输出i最小的。如果i相等，输出j最小的。
Input示例
6 10 1 2 3 4 5 6
Output示例
1 4
n＝10000，O（n^2）暴力能过。。。
const int maxn=1e4+10;
ll sum[maxn];
int main()
{ios::sync_with_stdio(false);int n,k;while(cin>>n>>k){int flag=1;int x,y,tmp;memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++){cin>>tmp;sum[i]=tmp+sum[i-1];}for(int i=0;i<n;i++)for(int j=i+1;j<=n;j++)if(sum[j]-sum[i]==k){flag=0;x=i+1;y=j;goto A;}A:;if(flag) cout<<"No Solution"<<endl;else cout<<x<<' '<<y<<endl;}return 0;
}
下面这个用map写的才是比较快的
const int maxn=1e4+10;
ll a[maxn],sum[maxn];
map<ll,ll>mp;
int main()
{ios::sync_with_stdio(false);int n,k;while(cin>>n>>k){mp.clear();memset(sum,0,sizeof(sum));for(int i=1;i<=n;i++){cin>>a[i];sum[i]=a[i]+sum[i-1];mp[sum[i]]++;}for(int i=0;i<n;i++)if(mp[sum[i]+k])for(int j=i;j<=n;j++){if(sum[j]-sum[i]==k){cout<<i+1<<' '<<j<<endl;goto A;}}cout<<"No Solution"<<endl;A:;}return 0;
}
这篇关于51nod 和为k的连续区间（map／暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
