51nod1094和为k连续区间（前缀和+map判断优化）

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1094

先上暴力代码

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=1e4+5;
 7 ll a[maxn],pre[maxn];
 8 
 9 int main()
10 {
11     ios::sync_with_stdio(false); cin.tie(0);
12     
13     ll n,k,sum;
14     cin>>n>>k;
15     for(int i=1;i<=n;i++) { cin>>a[i]; pre[i]=pre[i-1]+a[i]; }
16     
17     int f=0;
18     for(int i=1;i<=n;i++)
19     {
20         for(int j=i;j<=n;j++)
21         {
22             if(pre[j]-pre[i-1]==k)
23             {
24                 f=1;
25                 cout<<i<<' '<<j<<endl;
26                 break; 
27             }
28         }
29         if(f) break;
30     }
31     if(!f) cout<<"No Solution"<<endl;
32     
33     return 0;
34 }

map判断优化

分析和思路：

用map相当于把左边起点固定了，用map直接判断从这个起点往后是否有区间和为k序列存在，不存在就直接跳过，减少一轮遍历节省时间，map比普通标记数组大很多。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <map>
 4 #include <cmath>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e4+5;
 8 ll a[maxn],pre[maxn];
 9 map<ll,ll> mp;
10 
11 int main()
12 {
13     ios::sync_with_stdio(false); cin.tie(0);
14     
15     ll n,k,sum;
16     cin>>n>>k;
17     for(int i=1;i<=n;i++) { cin>>a[i]; pre[i]=pre[i-1]+a[i]; mp[pre[i]]++; }
18     
19     int f=0;
20     for(int i=1;i<=n;i++)
21     {
22         if(mp[pre[i-1]+k])//从i这个起点判断是否存在一段区间和为k,没有直接进行下一个,不做无用遍历 
23         for(int j=i;j<=n;j++)
24         {
25             if(pre[j]-pre[i-1]==k)
26             {
27                 f=1;
28                 cout<<i<<' '<<j<<endl;
29                 break; 
30             }
31         }
32         if(f) break;
33     }
34     if(!f) cout<<"No Solution"<<endl;
35     
36     return 0;
37 }

完