[ABC233]D - Count Interval（map + 前缀和）

题目传送门：D - Count Interval (atcoder.jp)

题目大意

各一个长度为N的序列，请问有多少个连续子串使得和为K？

思路

一开始想法是二分（下意识以为前缀和有单调性），但是后面发现因为数组中存在负数，所以无法保证前缀和的单调性，所以考虑使用map来记录在第i位之前，数字x出现的次数。

注意，一定要先把次数加进sum再对mp自增，不然可能出现自己减去自己的情况（没有意义）。

一开始要初始化mp[0] = 1，因为在前缀和数组中的第0位就是0，用于表示从第一个开始直到第i位的和。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5 + 10;

int A[maxn], prefix[maxn];

map<int, int> mp;

signed main()
{
	int N, K;cin >> N >> K;
	int sum = 0;
	mp[0] = 1;
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld",A + i);
		prefix[i] = prefix[i - 1] + A[i];
		
		sum += mp[prefix[i] - K];
		mp[prefix[i]] ++;
	}
	cout << sum << '\n';
	return 0;
}