企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

560.和为 K 的子数组

2、题目描述

二、个人思路整理

1、思路分析

核心思路：前缀和+哈希表。

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]
2. 等式转换：我们要找满足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
3. 哈希表优化（类似两数之和）：

• 遍历数组的同时维护当前的累加和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(vector<int>&nums,intk){// 哈希表用于记录 前缀和 出现的频次unordered_map<int,int>prefix_freq;prefix_freq[0]=1;// 前缀和为 0 出现了 1次intcurrent_sum=0;// 记录遍历过程中累加前缀和intcount=0;// 记录符合条件的子数组总数for(intnum:nums){current_sum+=num;// 更新当前的前缀和// 查找前面是否存在 prefix_sum 使得 current_sum - prefix_sum = k// 每一个对应的查询历史上等于 (current_sum - k) 的位置到当前位置都能构成一个和为 k 的子数组if(prefix_freq.count(current_sum-k)){count+=prefix_freq[current_sum-k];// 2026.10.25重做后： 注意count不是++}// 将当前前缀和加入哈希表prefix_freq[current_sum]++;}returncount;}};

三、知识风暴

前缀和（Prefix Sum）与哈希表（Hash Map）是解决连续子数组和问题的经典组合。其核心思想是将“子数组和”问题转化为“两数之差”问题，并利用哈希表实现O(1)时间的历史查询。

适用场景：

1. 子数组和问题：快速统计数组中满足特定和条件的连续子数组数量。
2. 累积统计问题：需要频繁查询任意区间和或区间统计信息。

关键思想：

• 前缀和转换：定义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 的最长子数组长度（求最长长度）