文章目录前言一、题目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 的最长子数组长度求最长长度