题目网址: https://www.luogu.com.cn/problem/U219423
题目作者: 含笑半步癫
Subsegments
题目描述
You are given an array of integers a1,a2,…,an and an integer x.
Output the number of subsegments [l,r] where 1<=l<=r<=n such that al+…+ar=x.
输入格式
The first line contains two integers n and x(1<=n<=500000,-987654321<=x<=987654321).
The second line contains n numbers a1,a2,…,an.
输出格式
Output one integer, the answer.
样例 #1
样例输入 #1
10 6
0 3 2 1 6 2 3 2 1 7
样例输出 #1
4
解题思路:
数据达到了500000,直接前缀和然后n^2扫一遍肯定超时。计算前缀和的同时对该前缀和出现的次数进行统计(用哈希unordered_map存,因为有负数输入这样比较方便)。每次循环的同时,直接在哈希表中找到和该前缀值能构成区间和等于x的前缀值(即timeTable[num[i]-x])累加。题目得解。
需要注意的是timeTable[0]需要给个初始值1,即为第0个数的前缀为0。
代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <string>
#include <unordered_map>
using namespace std;
#define MAX 500020
typedef long long ll;
ll num[MAX];
int cnt = 0;
unordered_map<ll, int> timeTable;
int main()
{
int n, x;
cin >> n >> x;
num[0] = 0;
timeTable[0]++;
for (int i = 1; i <= n; i++)
{
cin >> num[i];
num[i] += num[i - 1];
cnt += (timeTable[num[i] - x]);
timeTable[num[i]] ++;
}
cout << cnt;
}