新闻详情

新闻详情

首页 / 资讯中心 / 详情

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

发布时间:2026/11/21 8:54:30来源:尧图网络
刷题笔记:力扣第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。在本题要做到“用现在的状态去匹配过去的历史记录”每次查找的都是历史记录所以一定要坚守“先查后存”原则。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/20 0:44:51

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/19 15:17:14

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/20 20:45:42

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/20 16:11:20

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/20 18:41:01

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/20 0:44:55

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉