当前位置：首页 > news >正文

题解：AtCoder AT_awc0004_e Sum of Intervals

news 2026/4/29 1:02:27

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Sum of Intervals

【题目描述】

Takahashi has a sequence ofN NNintegersA = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, \ldots, A_N)A=(A1,A2,…,AN). Each elementA i A_iAimay take a negative value.
高桥有一个包含N NN个整数的序列A = ( A 1 , A 2 , … , A N ) A = (A_1, A_2, …, A_N)A=(A1,A2,…,AN)。每个元素A i A_iAi可能取负值。

Takahashi wants to select acontiguous subarrayfrom this sequence such that the sum of its elements is exactly equal to the integerK KK, whereK KKis the target sum value. Find the number of ways to choose such a subarray.
高桥希望从该序列中选择一个连续子数组，使得其元素之和恰好等于整数K KK（其中K KK是目标和值）。求选择这样的子数组的方式数量。

More precisely, find the number of pairs of integers( l , r ) (l, r)(l,r)satisfying1 ≤ l ≤ r ≤ N 1 \leq l \leq r \leq N1≤l≤r≤Nsuch that
更精确地说，求满足1 ≤ l ≤ r ≤ N 1 ≤ l ≤ r ≤ N1≤l≤r≤N且满足以下条件的整数对( l , r ) (l, r)(l,r)的数量：

A l + A l + 1 + ⋯ + A r = K A_l + A_{l+1} + \cdots + A_r = KAl+Al+1+⋯+Ar=K

【输入】

N NNK KK
A 1 A_1A1A 2 A_2A2⋯ \cdots⋯A N A_NAN

The first line contains the integerN NNrepresenting the number of elements in the sequence and the integerK KKrepresenting the target sum value, separated by a space.
The second line contains the integersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting each element of the sequence, separated by spaces.

【输出】

Print the number of pairs of integers( l , r ) (l, r)(l,r)that satisfy the condition, on a single line.

【输入样例】

5 5 1 2 3 4 5

【输出样例】

【解题思路】

【算法标签】

#前缀和#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,k;// n: 数组长度，k: 目标和inta[N],sa[N],ans;// a: 原始数组，sa: 前缀和数组，ans: 计数结果map<int,int>mp;// 用于存储前缀和出现的次数signedmain(){cin>>n>>k;// 读入数组长度和目标和mp[0]=1;// 初始化：前缀和为0出现1次（空子数组）for(inti=1;i<=n;i++){cin>>a[i];// 读入数组元素sa[i]=sa[i-1]+a[i];// 计算前缀和// 如果存在前缀和为sa[i]-k，则说明找到了和为k的子数组ans+=mp[sa[i]-k];// 将当前前缀和加入mapmp[sa[i]]++;}cout<<ans<<endl;// 输出和为k的子数组个数return0;}