D - 计数间隔（前缀和练习）（ABC 233）

D - 计数间隔（前缀和练习）（ABC 233）

原题连接：https://atcoder.jp/contests/abc233/tasks/abc233_d

大意就是给定n个数和一个数k，求有多少个区间能使 k = sum[l,r];

经典的前缀和问题，但如果最后用两重循环求的话，时间复杂度是O ( N2)，会超时，所以用map优化一下，这样一重循环就够了。

优化思路：

                  求 k = sum[r] - sum[l - 1]的个数，

                ​​​​​​​  可以变形为sum[l - 1]  = sum[r] - k；

                  那么可以先求出每个 sum[l - 1]的个数，

                  然后再看看有多少个 sum[r] - k的个数就行了。

这样只用一次for循环就可以了

另外，千万千万不要忘记开long long（忘记开ll就wa了，不要问我是怎么知道的......）

AC代码如下：

#include 
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n,k,s[N],x;
int main()
{
    cin >> n >> k;
    for (ll i = 1; i <= n; i++)//不要忘记等号
    {
        cin >> x;
        s[i] = s[i - 1] + x;//sum[i]的意思是前i个数的和
        
    }
    ll ans = 0;//记录答案；
    map  mp;
    for(ll i = 1; i <= n; i++)
    {
        mp[s[i - 1]]++;//记录每个左边界的个数

        ans += mp[s[i] - k];//如果有相等的就会加上
    }
    cout << ans;
}