1. 题目描述题目链接给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。注意子数组是数组中元素的连续非空序列。数组中可能包含负数。数据范围示例输入nums [1, 1, 1],k 2输出2解释共有两个子数组的和为 2分别是[1, 1](下标 0-1) 和[1, 1](下标 1-2)。2. 解法一暴力枚举2.1 核心思想最直观的思路是枚举所有的子数组并计算它们的和。我们可以使用两层循环外层循环i枚举子数组的左边界。内层循环j枚举子数组的右边界。在内层循环中维护一个变量sum累加从i到j的元素。如果sum k则计数器加一。2.2 代码实现 (C)class Solution { public: int subarraySum(vectorint nums, int k) { int ans 0; int n nums.size(); // 枚举左边界 i for (int i 0; i n; i) { int sum 0; // 每次更换左边界重置 sum // 枚举右边界 j for (int j i; j n; j) { sum nums[j]; // 累加当前元素 if (sum k) { ans; } // 注意这里不能因为 sum k 就 break因为数组中存在负数 } } return ans; } };2.3 复杂度分析时间复杂度O(N2)。有两层嵌套循环空间复杂度O(1)。只使用了常数级别的额外空间。3. 解法二前缀和 哈希表最优解暴力解法的时间瓶颈在于对于每个右边界j我们都重新计算了从i到j的和。我们可以利用前缀和来优化这个计算过程。3.1 核心推导定义preSum[i]为数组从第 0 个元素到第i个元素的总和。那么子数组nums[i...j]的和可以表示为Sum(i,j)preSum[j]−preSum[i−1]题目要求Sum(i, j) k代入公式得preSum[j]−preSum[i−1]k移项得preSum[i−1]preSum[j]−k当我们遍历到位置j时我们只需要知道在j之前有多少个前缀和等于preSum[j] - k即可。3.2 哈希表的作用为了快速查询“之前出现过多少次某个前缀和”我们可以使用哈希表 (unordered_map)。Key前缀和的值。Value该前缀和出现的次数。3.3 细节处理初始化map[0] 1这是为了处理从数组起始位置 (索引 0) 开始的子数组。如果preSum[j]本身就等于k那么preSum[j] - k 0此时我们需要哈希表里存在0这个前缀和且次数为 1。边遍历边更新先计算当前preSum去哈希表里查找preSum - k的次数累加到ans然后再把当前的preSum放入哈希表。顺序不能颠倒否则会把自己也算进去导致错误。3.4 代码实现 (C)class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int mp; // 初始化前缀和为0的情况出现了1次 mp[0] 1; int preSum 0; // 记录当前前缀和 int ans 0; // 记录结果 for (int i 0; i nums.size(); i) { preSum nums[i]; // 计算到当前位置的前缀和 // 核心逻辑如果 (当前前缀和 - k) 在哈希表中存在 if (mp.find(preSum - k) ! mp.end()) { ans mp[preSum - k]; } // 将当前前缀和存入哈希表 mp[preSum]; } return ans; } };3.5 复杂度分析时间复杂度O(N)。只需要遍历一次数组哈希表的插入和查找操作平均时间复杂度为 O(1)。空间复杂度O(N)。最坏情况下数组中的每个元素都会产生不同的前缀和哈希表需要存储 N 个键值对。