2015번: 수들의 합 4

https://www.acmicpc.net/problem/2015



$O(n\lg n)$

s[i]: 1...i 번째 수들의 합
s[i]-s[j]=k(j<i)인 i,j를 찾아야 하므로
모든 X=s[j]인 j(j<i)의 개수를 구해놓으면 해결할 수 있다.

#include<cstdio>
#include<map>
using namespace std;
int s, x, n, k;
map<int, int> mp;
long long r;
int main() {
    mp[0]++;
    for (scanf("%d%d", &n, &k); n--;) {
        scanf("%d", &x);
        s += x;
        r += mp[s - k];
        mp[s]++;
    }
    printf("%lld", r);
    return 0;
}