Subsegments(和为X的子数组)

来源： 剑指offer II 010.和为k的子数组

题目描述

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.

输入样例

10 6
0 3 2 1 6 2 3 2 1 7

输出样例

4

C++代码如下：

#include 
#include 

using namespace std;

const int N = 500010;
typedef long long LL;
LL a[N];
int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    LL sum = 0, res = 0;
    unordered_map cnt;
    cnt[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        sum += a[i - 1];
        if(cnt[sum - x] > 0)
            res += cnt[sum - x];
        cnt[sum] ++;
    }
    printf("%d", res);
    return 0;
}

几周前校赛的一道题，当时一直想用滑动窗口解决，但由于范围存在负数无法解决这个问题。

前缀和差值理解:举个例子

按输入输出样例:当读到6时,此时sum = 12, sum - x = 6, 这就意味着以0为起点以6为终点的sum比目标距离多出6,然而在此前我们已经找到了sum = 6的位置 即读到0 3 2 1时距离恰好为6, 故6为一个解,其他情况类似。

后面只解释cnt[0] = 1的用处:还是举个例子

比如我们的数组为 3 2 1 6 2 3 2 1 7
我们的X = 6，当我们计算到3 2 1时，累加和sum已经为6了，
此时我们进行计算，如果没把前缀和cnt[0]=1存放到哈希表里，那么cnt[cnt - X]就不会存在了