刷题笔记:力扣第560题-和为k的子数组-北京尧图网络

1.拿到本题后首先想到的是滑动窗口法设置左右指针l和r右指针一直前进当前子数组和大于等于k时左指针也前进和为k的时候结果计数值1。完整代码如下1. int subarraySum(int* nums, int numsSize, int k) { 2. int l 0, r 0; 3. int cnt 0; 4. int sum 0; 5. 6. while (r numsSize){ 7. sum nums[r]; 8. while (l r sum k){ 9. if (sum k) cnt; 10. sum - nums[l]; 11. } 12. } 13. 14. return cnt; 15. }2.需要注意两点1当子数组和大于k时左指针只前进一步不一定能将和重新变成小于k所以判断代码应该用while而不是if。2内部while循环需要记得加l r边界条件防止越界且一定不能有等于号因为当执行完sum nums[r]后r可能就已经越界了但此时仍在while循环内部此时若允许l r就会导致l越界。3.滑动窗口方法在本题是不正确的因为本题的数组中出现了负数这样就不满足“右指针前进子数组和一定变大左指针前进子数组和一定变小”的核心逻辑。本题正确的方法是使用“前缀和”前缀和sum[i]的含义为数组从0到i所有元素的和。设和为k的子数组为[i, i1,… j]则可以得出sum[j] - sum[i – 1] k经过移项可得sum[i – 1] sum[j] – k所以只需要设置一个哈希表将所有前缀和统计进去每次寻找sum[i – 1]并将它的次数加到结果中即可。4.基于以上思想可写出完整代码如下1. // uthash哈希节点key保存前缀和cnt保存该前缀和出现的次数 2. typedef struct { 3. int key; 4. int cnt; 5. UT_hash_handle hh; 6. } HashEntry; 7. 8. // 子数组和为k的数量前缀和哈希表优化 9. int subarraySum(int* nums, int numsSize, int k) { 10. // 哈希表头初始化为空 11. HashEntry* hashTable NULL; 12. HashEntry* entry NULL; 13. // 初始化前缀和0出现次数为1对应前缀和从0开始的基准 14. entry (HashEntry*)malloc(sizeof(HashEntry)); 15. entry-key 0; 16. entry-cnt 1; 17. HASH_ADD_INT(hashTable, key, entry); 18. // res记录符合条件子数组总数 19. int res 0; 20. // sum记录当前前缀和 21. int sum 0; 22. // 遍历数组计算前缀和 23. for (int i 0; i numsSize; i){ 24. sum nums[i]; 25. // 需要查找的前缀和sum - k 26. int target sum - k; 27. HashEntry* tmp NULL; 28. // 在哈希表查找target前缀和 29. HASH_FIND_INT(hashTable, target, tmp); 30. // 如果存在累加它出现的次数到结果 31. if (tmp) res tmp-cnt; 32. // 查找当前前缀和sum准备更新哈希表 33. HASH_FIND_INT(hashTable, sum, tmp); 34. if (tmp NULL){ 35. // 不存在该前缀和新建节点加入哈希表次数初始化为1 36. tmp (HashEntry*)malloc(sizeof(HashEntry)); 37. tmp-key sum; 38. tmp-cnt 1; 39. HASH_ADD_INT(hashTable, key, tmp); 40. } else { 41. // 已存在次数1 42. tmp-cnt; 43. } 44. } 45. return res; 46. }该算法时间复杂度和空间复杂度均为O(n)。5.需要注意在一开始需要将“前缀和为0”直接放进哈希表中出现次数为1。这样才能保证“当前前缀和正好等于k”时能正确地将结果1。6.本题核心代码中一定要保证“先查找前缀和再添加当前前缀和”。因为当k 0时如果先添加了当前前缀和就会在后续查到自己导致结果错误地多加了1。在本题要做到“用现在的状态去匹配过去的历史记录”每次查找的都是历史记录所以一定要坚守“先查后存”原则。

刷题笔记:力扣第560题-和为k的子数组

相关推荐

商汤办公小浣熊接入OpenClaw生态，TaoToken统一Key打通AI智能体配置链路

Kimi K2 + Claude Code 配 TaoToken：settings.json 骨架与验证动作

Skills实战指南：从Prompt到技能包，高效驾驭AI编程

更多资讯

Prompt 还是 Skill？best-skills 终极解析：为什么 Agent 自动判断调用比手动粘贴更高效

C++异常处理最佳实践：从错误模型到RAII与安全设计

AI写代码、不画帧：Opus 5.5+Python+FFmpeg生成30秒粒子动画全解析

基于Dify的AI对话复盘系统：让大模型应用具备事后反思能力

MMagic 社区贡献实战指南：从 Fork 到 Pull Request 的完整协作流程与工程规范

软件测试必备：每天5分钟掌握SQL查询与INSERT数据操作

今日更新

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

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

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

本周精选

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

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

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

本月热门

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

分布式服务的决策记录

创业产品的首版范围

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