【leetcode复健-8】560. 和为 K 的子数组-前缀和思想+哈希表

560. 和为 K 的子数组 - 力扣（LeetCode）

给你一个整数数组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

坑点与要点

我们首先理清楚题目要求：
1. 找nums中连续子数组，和为k
2. 返回子数组个数

相信大多数人都会通过看示例来快速理解题目，但这题需要额外关注的是，示例所给出的数组都是有序的，而我们实际接收到的数组是无序的，一定不能被示例所误导
这题的正确题解很巧妙，使用前缀和的思想，将前缀和保存在一张哈希表中，此后我们只需要关注哈希表中有多少个的前缀之和与当前数组前缀之和的差能够等于k即可，如此这道题就转换成了与1. 两数之和 - 力扣（LeetCode）同类型的题目。

正确思路

两个前缀和之差确定一个数组。

使用一张哈希表 hash1 来记录当前所有前缀（键为数值前缀和，值对应的前缀和个数），cnt 记录满足和为 k 的子数组个数，变量 prefix （前缀和）从数组起始点开始不断累加，每次循环将当前的前缀和个数 +1 ，并计算 seen = k - prefix ，seen 代表当前前缀数组要到达 k 所需要的前缀和，在 hash1 中查询所需要的前缀和个数，将其累加到 cnt 中。
如此即可找出所有符合要求的子数组个数

代码如下

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: hash1 = {} hash1[0] = 1 prefix = 0 seen = 0 cnt = 0 for i in nums: prefix += i seen = prefix - k if seen in hash1: cnt += hash1[seen] if prefix in hash1: hash1[prefix] += 1 else: hash1[prefix] = 1 return cnt

精华思路

以后遇到连续的字符串/数组这类题目，不仅可以考虑双指针，也可以考虑使用前缀和思想尝试等价替代