给你一个整数数组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]题目要求它等于kprefix[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的出现次数时间开销肯定会加大的