【子串】LC 560.和为 K 的子数组-北京尧图网络

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接560.和为 K 的子数组2、题目描述二、个人思路整理1、思路分析核心思路前缀和哈希表。子数组和与前缀和的关系定义prefix_sum[i]为前i ii个元素的和令prefix_sum[0] 0。任意连续子数组nums[j..i-1]的和可以表示为sum ( j , i − 1 ) prefix_sum [ i ] − prefix_sum [ j ] \text{sum}(j, i-1) \text{prefix\_sum}[i] - \text{prefix\_sum}[j]sum(j,i−1)prefix_sum[i]−prefix_sum[j]等式转换我们要找满足sum ( j , i − 1 ) k \text{sum}(j, i-1) ksum(j,i−1)k的子数组即prefix_sum [ i ] − prefix_sum [ j ] k ⟺ prefix_sum [ j ] prefix_sum [ i ] − k \text{prefix\_sum}[i] - \text{prefix\_sum}[j] k \iff \text{prefix\_sum}[j] \text{prefix\_sum}[i] - kprefix_sum[i]−prefix_sum[j]k⟺prefix_sum[j]prefix_sum[i]−k哈希表优化类似两数之和遍历数组的同时维护当前的累加和current_sum。查询哈希表中已出现过的前缀和中有多少个等于current_sum - k将其出现次数累加到答案中。将当前的current_sum记录到哈希表中频次 1。关键边界条件初始化 {0: 1}哈希表必须预先存入mp[0] 1。这代表“前缀和为 0 出现过 1 次”用来处理从下标 0 开始的子数组和恰好等于k kk的情况即current_sum - k 0。复杂度分析时间复杂度O ( n ) O(n)O(n)只需单次遍历数组哈希表单次存取平均时间为O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)哈希表最多存储O ( n ) O(n)O(n)个不同的前缀和。2、解题代码classSolution{public:intsubarraySum(vectorintnums,intk){// 哈希表用于记录前缀和出现的频次unordered_mapint,intprefix_freq;prefix_freq[0]1;// 前缀和为 0 出现了 1次intcurrent_sum0;// 记录遍历过程中累加前缀和intcount0;// 记录符合条件的子数组总数for(intnum:nums){current_sumnum;// 更新当前的前缀和// 查找前面是否存在 prefix_sum 使得 current_sum - prefix_sum k// 每一个对应的查询历史上等于 (current_sum - k) 的位置到当前位置都能构成一个和为 k 的子数组if(prefix_freq.count(current_sum-k)){countprefix_freq[current_sum-k];// 2026.10.25重做后注意count不是}// 将当前前缀和加入哈希表prefix_freq[current_sum];}returncount;}};三、知识风暴前缀和Prefix Sum与哈希表Hash Map是解决连续子数组和问题的经典组合。其核心思想是将“子数组和”问题转化为“两数之差”问题并利用哈希表实现O(1)时间的历史查询。适用场景子数组和问题快速统计数组中满足特定和条件的连续子数组数量。累积统计问题需要频繁查询任意区间和或区间统计信息。关键思想前缀和转换定义prefix[i]为前i个元素之和。任意子数组nums[j..i-1]的和可表示为prefix[i] - prefix[j]。哈希表优化将问题prefix[i] - prefix[j] k转化为寻找历史上是否存在prefix[j] prefix[i] - k。遍历时用哈希表记录每个前缀和出现的次数即可在O(1)时间内得到以当前位置结尾的、和为k的子数组数量。初始化技巧哈希表预先存入{0: 1}以处理从数组开头开始的子数组即prefix[i] - 0 k。相关 LeetCode 例题560. 和为 K 的子数组本题523. 连续的子数组和涉及模运算974. 和可被 K 整除的子数组前缀和与同余定理325. 和等于 k 的最长子数组长度求最长长度

【子串】LC 560.和为 K 的子数组

相关推荐

IINA 免费 Mac 视频播放器安装与字幕设置完整指南

从 2007 年到 2026：OpenCore Legacy Patcher 让老 Mac 完整升级最新 macOS 的实战指南

k8s漏洞学习

更多资讯

亿级流量系统架构设计：高并发挑战与解决方案

100kW导热油炉工业应用与控制系统详解

Vivado+Verilog单周期CPU设计：MIPS数据通路与上板调试

UR5机械臂MATLAB轨迹规划：DH建模、插补与奇异避坑

Linux HISTFILE环境变量详解与实用技巧

云服务器部署Dify：AI应用开发平台搭建指南

今日更新

基于YOLOv11的石油泄漏智能检测系统开发实践

AI行业变局：合规、Mod化与上下文管理的实战启示

计算机视觉与AI原生应用融合的技术实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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