LeetCode hot 100 —560. 和为 K 的子数组
给你一个整数数组
nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2输出：2示例 2：
输入：nums = [1,2,3], k = 3输出：2提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
不知道为什么做了滑动窗口和双指针以后，总想用left and right来做很多题目
但在第一版本敲代码的时候就知道这里不适合用了。
首先是数组是无序的，左移和右移并不能完全的对应减和加；所以带来的衍生点是，比如说现在找到了一个合适的子数组，我的Left和 right 要怎么更新我完全没有头绪
然后我想到了差分。也是当时练习csp的入门算法。
和GPT对了一下思路，除了差分，还有一个东西叫前缀和，算是差分的进阶版（太久没用了已经不是我的第一反应了....），也就是前n个数字的和是多少
假设定义：
prefix[i] = nums 前 i 个数字之和那么从下标left到right的子数组和可以表示成：
prefix[right + 1] - prefix[left]题目要求它等于k：
prefix[right + 1] - prefix[left] = k把这个式子移动一下：
prefix[left] = prefix[right + 1] - k现在先别急着写代码，只思考：当我从左向右计算到一个新的前缀和current时，我需要在之前出现过的前缀和里寻找什么值？（前缀和为current - k的）再进一步思考：题目问的是子数组的“个数”，如果要找的那个前缀和值在前面出现了多次，意味着什么？
尝试手算：
nums = [1, -1, 1] k = 1它的前缀和（记得最开始还有一个“尚未选择任何数字”的前缀和0）是：
0, 1, 0, 1当你走到最后一个前缀和1时，需要寻找：
1 - k = 0此前0出现了不止一次。每一个此前出现的0，都对应一个以当前位置结尾、和为1的子数组。
因此你下一步只需要回答两个问题：
- 如何一边遍历，一边记录此前每个前缀和出现了多少次？
- 如何快速查询
当前前缀和 - k此前出现了多少次？
想清楚这两点，就不再需要控制left和right了。这里的思维转换是：不要直接维护一个窗口，而是把每个可能的左边界压缩成“此前出现过的前缀和统计”。
最后的代码如下：
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # 构造前缀和 prefix_cnt = {0: 1} """ 这个也算是看了GPT给的答案以后受到的大启发，我给的一个注释和思维解释是： 这道题目需要前缀和，但为什么不使用常规的前缀和数组呢？ - 因为我最后需要统计的是res_count，也就是我需要统计的是个数 我知道了当前的前缀和为current, 我需要找的值是current - k,我需要统计的东西是current - k 出现了多少次，所以这里用的是一个dict的形式，可以更快的知道某个前缀和已经出现的次数. - 为什么要初始化一个0 : 1：确保nums[0]也可以被划入. 比如当前current == k，那么就是nums[0:index + 1]可以计入一次，但是如果没有0，这个答案不会被计入。 """ res = 0 prefix_sum = 0 #记录前缀和 for num in nums: prefix_sum += num res += prefix_cnt.get(prefix_sum - k, 0) """ dict.get(key, default) 表示： - 如果字典中存在 key，返回对应的值。 - 如果不存在，返回 default。 """ prefix_cnt[prefix_sum] = ( prefix_cnt.get(prefix_sum, 0) + 1 ) return res总结一下，感觉GPT启发的核心是：
先找准算法结构，用什么。双指针，还是我想到的差分，及其进阶版的前缀和？
从答案反推数据结构，数据结构是统计上面的优化，什么样的数据结构载体可以更快的得到答案？（比如这里如果用前缀和数组的话，每遇到一个前缀和就要去统计current - k的出现次数，时间开销肯定会加大的）