Eric 的小站

【题目描述】#

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

【示例 1】： 输入：nums = [1,1,1], k = 2 输出：2

【示例 2】： 输入：nums = [1,2,3], k = 3 输出：2

【思路分析】#

这道题的目标是： 1.找出数组中和为 k 的子数组的数量。 2.子数组是连续的一段数组元素。

对于这类问题，我们可以用两种主要的解法： **暴力解法：**枚举所有可能的子数组，计算其和，统计和为 k 的子数组数量。

• 时间复杂度高，为 𝑂(𝑛^2) **前缀和 + 哈希表：**通过记录前缀和出现的次数，快速判断是否存在符合条件的子数组。
• 时间复杂度为 𝑂(𝑛)

前缀和的定义 前缀和的本质是从数组起点到当前位置的累加和。假设有一个数组 nums = [1, 2, 3, 4]：

• 它的前缀和数组是 [1, 3, 6, 10]。
  • 1 = 1 (第一个元素)
  • 3 = 1 + 2 (前两个元素的和)
  • 6 = 1 + 2 + 3 (前三个元素的和)
  • 10 = 1 + 2 + 3 + 4 (前四个元素的和)

子数组和与前缀和的关系 如果我们需要计算数组中某一段的子数组和，例如子数组 nums[i]，它的和可以表示为： sum(𝑛𝑢𝑚𝑠[𝑖<𝑗>])=prefix_sum[𝑗]−prefix_sum[𝑖−1]

• 其中，prefix_sum[j] 是从开头到第 j 个元素的累加和；
• prefix_sum[i-1] 是从开头到第 i-1 个元素的累加和；
• 差值就是从第 i 到第 j 的子数组和。

例如：

• 对于数组 nums = [1, 2, 3, 4]：
  • 要找子数组 [2, 3] 的和，可以用前缀和 prefix_sum[2] - prefix_sum[0] = 6 - 1 = 5。

用前缀和高效解决问题的核心思路 子数组和的问题可以用前缀和巧妙解决：

1.遍历数组时，我们计算当前位置的前缀和。 2.如果某段子数组的和等于目标值 k，我们可以用公式： prefix_sum[j]−prefix_sum[i−1]=k 转换为： prefix_sum[i−1]=prefix_sum[j]−k 3.也就是说，只要前面某个前缀和等于当前前缀和减去目标值 k，就存在一个子数组的和为 k。 4.用一个哈希表（unordered_map）记录前缀和出现的次数，可以快速判断这种情况，并累加满足条件的次数。

对于本题具体实现步骤

初始化 1.使用一个变量 currentSum 来记录当前的前缀和。 2.用一个哈希表 prefixSum 来记录每个前缀和出现的次数，初始时存入 prefixSum[0] = 1（表示前缀和为 0 出现了 1 次，处理初始情况）。 3.定义一个变量 answer 来统计满足条件的子数组数量。

遍历数组 对于数组中的每个元素： 1.更新当前的前缀和：currentSum += nums[i]。 2.检查哈希表中是否存在 currentSum - k：

• 如果存在，说明从某个位置到当前的子数组和为 k，将对应的次数加到 answer 中。 3.将 currentSum 更新到哈希表中，表示当前前缀和出现了一次。

返回结果 遍历结束后，answer 就是满足条件的子数组数量。

【C++解答】#

1
class Solution {
2
public:
3
    int subarraySum(vector<int>& nums, int k) {
4
        // 使用前缀和 + 哈希表
5
        unordered_map<int, int> prefixSum;
6
        prefixSum[0] = 1; // 初始条件，前缀和为0时的出现次数为1
7
        int currentSum = 0;
8
        int answer = 0;
9

10
        for (int num : nums) {
11
            currentSum += num; // 更新当前的前缀和
12

13
            // 检查是否存在以当前元素结尾的子数组和为k
14
            if (prefixSum.find(currentSum - k) != prefixSum.end()) {
15
                answer += prefixSum[currentSum - k];
16
            }
17

18
            // 更新前缀和的出现次数
19
            prefixSum[currentSum]++;
20
        }
21

22
        return answer;
23
    }
24
};