题目大意 给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。 解题思路 首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。 枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。 参考代码 方法一：map 方法二：离散化

一.题意一.题意一.题意 求一个序列有多少子段之和为k求一个序列有多少子段之和为k求一个序列有多少子段之和为k 二.思路二.思路二.思路 看到子段第一时间想到的肯定是双指针，但是ai可能小于0所以对于同一个左/右端点可能会有多个解，不可行看到子段第一时间想到的肯定是双指针，但是a_i可能小于0所以对于同一个左/右端点可能会有多个解，不可行看到子段第一时间想到的肯定是双指针，但是ai 可能小于0所以对于同一个左/右端点可能会有多个解，不可行 我们看到每个子段[li,ri]的值都是∑i=liria[i]=a[li]+a[li+1]+a[li+2]+⋯+a[ri]，那我们必定能想到前缀和我们看到每个子段[l_i,r_i]的值都是\sum_{i=l_i}^{r_i}a[i]=a[l_i]+a[l_i+1]+a[l_i+2]+\cdots+a[r_i]，那我们必定能想到前缀和我们看到每个子段[li ,ri ]的值都是∑i=li ri a[i]=a[li ]+a[li +1]+a[li +2]+⋯+a[ri ]，那我们必定能想到前缀和 设sum[i]是下标1至i中所有数的和，那么这段子段的值就是sum[ri]−sum[li−1]设sum[i]是下标1至i中所有数的和，那么这段子段的值就是sum[r_i]-sum[l_i-1]设sum[i]是下标1至i中所有数的和，那么这段子段的值就是sum[ri ]−sum[li −1] 那对于每个ri我们都找满足条件的sum[li]并计数不就可以了么那对于每个r_i我们都找满足条件的sum[l_i]并计数不就可以了么那对于每个ri 我们都找满足条件的sum[li ]并计数不就可以了么 具体的，对于1≤ri≤n我们要找的是1≤li<ri且sum[ri]−sum[li−1]=k即sum[li−1]=sum[ri]−k具体的，对于1\le r_i\le n我们要找的是1\le l_i < r_i且sum[r_i]-sum[l_i-1]=k即sum[l_i-1]=sum[r_i]-k具体的，对于1≤ri ≤n我们要找的是1≤li <ri 且sum[ri ]−sum[li −1]=k即sum[li −1]=sum[ri ]−k 便可以用map存sum[li]在对于所有的i找sum[j]=sum[ri]−k便可以用map存sum[l_i]在对于所有的i找sum[j]=sum[r_i]-k便可以用map存sum[li ]在对于所有的i找sum[j]=sum[ri ]−k 注意因为j=li−1所以j可以为0注意因为j=l_i-1所以j可以为0注意因为j=li −1所以j可以为0 三.小练习三.小练习三.小练习 ① A.A.A.{0,0} B.B.B.{sum[1],1} C.C.C.{0,1} D.D.D.{sum[1],0} ② A.A.A.<= B.B.B.== C.C.C.>= D.D.D.!= ③ A.A.A.tmp B.B.B.k C.C.C.sum[i] D.D.D.i ④ A.A.A.<= B.B.B.== C.C.C.>= D.D.D.!= ⑤ A.A.A.{sum[tmp],1} B.B.B.{sum[i],1} C.C.C.{sum[tmp],0} D.D.D.{sum[i],0} 四.正解四.正解四.正解 参考答案:CDABD参考答案:CDABD参考答案:CDABD 求点赞求点赞求点赞

前缀和 + 哈希表 O(N) 求解子数组和等于K的个数 题目描述 小午有一个长度为 nnn 的数组 aaa，下标从 1 开始，小枫有一个整数 kkk。 小枫想知道数组 aaa 的所有连续子序列中，有多少个元素之和等于 kkk。 形式化地，有多少对 (l,r)(l, r)(l,r) 满足以下条件： * 1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n * ∑i=lrai=k\sum_{i=l}^{r} a_i = k∑i=lr ai =k 输入格式 第一行输入两个整数 n,kn, kn,k，分别表示数组长度以及要求的元素之和。 第二行输入 nnn 个整数 aia_iai ，表示数组中第 iii 个元素的大小。 输出格式 输出一个整数，表示元素之和等于 kkk 的连续子序列的个数。 解题思路 1. 前置知识：前缀和 定义前缀和数组 sss： * s[0]=0s[0] = 0s[0]=0 * s[i]=a1+a2+⋯+ais[i] = a_1 + a_2 + \dots + a_is[i]=a1 +a2 +⋯+ai （数组下标从 1 开始） 子数组 a[l…r]a[l…r]a[l…r] 的和可以表示为： ∑i=lrai=s[r]−s[l−1]\sum_{i=l}^{r} a_i = s[r] - s[l-1] i=l∑r ai =s[r]−s[l−1] 我们的目标是找到所有满足 s[r]−s[l−1]=ks[r] - s[l-1] = ks[r]−s[l−1]=k 的 (l,r)(l, r)(l,r) 对，等价于找有多少个 s[l−1]s[l-1]s[l−1] 等于 s[r]−ks[r] - ks[r]−k。 2. 朴素暴力解法（超时） * 预处理出完整的前缀和数组 sss； * 枚举所有子数组的起点 lll 和终点 rrr（1≤l≤r≤n1 \le l \le r \le n1≤l≤r≤n）； * 计算 s[r]−s[l−1]s[r] - s[l-1]s[r]−s[l−1] 并统计等于 kkk 的次数。 缺点：时间复杂度为 O(n2)O(n^2)O(n2)，对于 n=2e5n=2e5n=2e5 的数据范围会超时。 3. 前缀和 + 哈希表优化（最优解） 核心思想：遍历到位置 rrr 时，只需知道前面有多少个 s[l−1]s[l-1]s[l−1] 等于 s[r]−ks[r] - ks[r]−k，这个数量就是以 rrr 为终点的、和为 kkk 的子数组个数。 具体步骤： 1. 初始化哈希表 mp，mp[0] = 1（对应 s[0]=0s[0]=0s[0]=0，确保能统计从数组开头到当前位置的子数组）； 2. 遍历数组，实时计算当前前缀和 sss（无需存储整个前缀和数组，节省空间）； 3. 查询哈希表中 s−ks - ks−k 的出现次数，累加到答案 ans； 4. 将当前前缀和 sss 加入哈希表（计数 + 1）； 5. 遍历结束后，ans 即为最终结果。 代码实现 方法一：朴素暴力解法（O(N²) 超时） ###方法二：前缀和 + 哈希表优化 O（n） AC

map秒了