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]题目要求它等于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的出现次数时间开销肯定会加大的

LeetCode hot 100 —560. 和为 K 的子数组

相关推荐

零代码有声书制作：用ebook2audiobook轻松实现电子书转语音

Glean部署教程：Docker Compose一键启动，轻松管理服务依赖

多‑Agent 电商推荐系统完整搭建教程（原理+架构+可运行代码+模块图解+部署）

更多资讯

Agent训练场架构设计：日跑300万沙箱的评分与防作弊实践

AI 伦理与安全

免费网页翻译插件，支持英文页面双语对照阅读

秋日晨拍新诗——颗颗新绿肺晶莹，吐纳蕴育气真香

DeepAgents+MCP+A2A+Skills：构建可编排可扩展的多智能体集群

新人的第一篇文章

今日更新

开源模型端侧落地实战：量化、推理加速与Agent上下文管理

AI Evals实战指南：从零搭建LLM应用评估体系与CI/CD集成

Java采购管理系统实战：从数据库设计到事务一致性

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？