题目大概：
给定一个长度为n的整数数组和一个整数k，你需要找到该数组中和为k的连续子数组的个数，
测试样例：
输入：
5 3
1 1 2 1 1
输出：
2
思路1：
利用for循环暴力枚举子数组，并且求和+计数，时间复杂度为O(n^3)。（如果数据大于了100，这个思路绝对Time Limit Exceeded(时间超时),所以要进行优化）！
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k; //定义
scanf("%d%d",&n,&k); //输入
int a[n],sum=0; //定义数组和计数器
for(int i=0;i<n;i++) //for循环输入
scanf("%d",a[i]); //输入下标为i的数
for(int i=0;i<n;i++){ //区间i枚举
for(int j=0;j<n;j++){ //区间j枚举
int ans=0; //区间和计数数组
for(int x=i;x<=j;x++) //求出区间[i,j]的和
ans+=a[i]; //计数
if(ans==k) //比较
sum++; //计数
}
}
cout<<sum<<endl; //输出
return 0;
}
思路2：
我们还可以使用前缀和来解决这个问题，首先预处理出a的前缀数组sum，每次求出子数组的和，然后进行双重循环的区间枚举，然后与k进行比较,时间复杂度为O(n^2).(如果数据不大于1500，是可以AC的，还有优化空间)。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k; //定义
scanf("%d%d",&n,&k); //输入
int sum[n+1]={0},ans=0; //定义前缀和数组sum和计数器ans
sum[0]=0; //将下标为0的地址初始化为0
for(int i=1;i<=n;i++){ //进行循环n次读入
int a; //定义
scanf("%d",&a); //输入
sum[i]=sum[i-1]+a; //求前缀和
}
for(int i=1;i<=n;i++) //区间枚举i
for(int j=0;j<n;j++) //区间枚举j
if(sum[i]-sum[j]==k) //求出区间[i,j]的和与k比较
ans++; //计数器加1
cout<<ans<<endl; //输出计数器
return 0; //结束
}
思路3：
我们可以使用map(STL库定义的类)，加上前缀和进行优化。在单用前缀和的思路中,我们要求一个结尾下标为i的子数组的和是否为k,就需要对j从0开始遍历到i-1,来找到是否存在sum[i]-k=sum[j]。那么我们只用map来存前i个元素的前缀和，把出现的次数(>i)之前的前缀和的值保存下来，最后判断map中是否包含sum[i]-k即可。
时间复杂度为O(n),已经算是很快的了，数据大到几百万都可以AC了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k; //定义
scanf("%d%d",&n,&k); //输入
int sum[n+1]={0},ans=0; //定义前缀和数组sum和计数器ans
sum[0]=0; //将下标为0的地址初始化为0
map<int,int> p; //定义map
for(int i=1;i<=n;i++){ //进行循环n次读入
int a; //定义
scanf("%d",&a); //输入
sum[i]=sum[i-1]+a; //求前缀和
p[sum[i]]++; //进行存储
}
for(int i=0;i<n;i++) //进行区间判断
ans+=p[sum[i]+k]; //计数
cout<<ans<<endl; //输出
return 0; //结束
}
总结：
该题是前缀和中很经典的一道题目，相当于敲门砖了，后面还有更难的差分、二维前缀和等……
