この問題の解法はほとんどAGC 023 Zero-Sum Rangesと同様です
N-Sum Ranges
S を長さ N+1 の数列とし、S0=0,Si=Si−1+Ai とします。
ある連続する部分列の総和は、
S の 2 要素の差です。
よって、和が K になる連続する部分列の数は、S の2点i,j(i<j)を選び,Sj−Si=Kとなる i,jを選ぶ方法の数に等しいです。
これは、S の要素に それぞれの数字が何回出てきたかをmap などでカウントしておき、Sの要素iに対してmap内にあるSi−Kの数の和が答えとなります。
よってこの問題は O(N)で解けました