【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中连续子数组和为k2. 返回子数组个数相信大多数人都会通过看示例来快速理解题目但这题需要额外关注的是示例所给出的数组都是有序的而我们实际接收到的数组是无序的一定不能被示例所误导这题的正确题解很巧妙使用前缀和的思想将前缀和保存在一张哈希表中此后我们只需要关注哈希表中有多少个的前缀之和与当前数组前缀之和的差能够等于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精华思路以后遇到连续的字符串/数组这类题目不仅可以考虑双指针也可以考虑使用前缀和思想尝试等价替代