该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

和为 K 的子数组

题目描述

给定一个整数数组 $nums$ 和一个整数 $k$，请你统计并返回该数组中和为 $k$ 的连续非空子数组的个数。

子数组定义为数组中元素的连续非空序列。

输入格式

第一行两个整数 $n$ 和 $k$，分别表示数组的长度和目标和。

第二行 $n$ 个整数，表示数组 $nums$ 的元素。

输出格式

一行一个整数，表示满足条件的子数组的个数。

样例 #1

样例输入 #1

3 2
1 1 1

样例输出 #1

2

样例解释 #1

满足条件的子数组有两个：

• 第 1 个和第 2 个元素组成的子数组 $[1,1]$，和为 $2$
• 第 2 个和第 3 个元素组成的子数组 $[1,1]$，和为 $2$

样例 #2

样例输入 #2

4 3
1 2 3 0

样例输出 #2

3

样例解释 #2

满足条件的子数组有三个：

• $[1,2]$，和为 $3$
• $[3]$，和为 $3$
• $[3,0]$，和为 $3$

提示

数据范围与约定

• 对于 $100\%$ 的数据，保证：
  • $1 \le n \le 2 \times 10^4$
  • $-1000 \le nums_i \le 1000$
  • $-10^7 \le k \le 10^7$

算法提示

1. 暴力枚举法：枚举所有子数组的起点和终点，计算和并统计。时间复杂度 $O(n^2)$，无法通过全部测试点。
2. 前缀和 + 哈希表优化（推荐）：