LeetCode 560. 和为 K 的子数组

有一说一，这道题我不会写（只会暴力n^2），没看题解让GPT帮我想的。

【题目描述】

给你一个整数数组 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:j]，它的和可以表示为：
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++解答】

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

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

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

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

        return answer;
    }
};