LeetCode-前缀和-和为K的子数组
✏️ 关于专栏：专栏用于记录
prepare for the coding test。
文章目录
📝 和为K的子数组
🎯题目描述
给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。
🔗题目链接：和为K的子数组
🔍 输入输出示例
示例 1:
输入：nums = [1,1,1], k = 2
输出：2
示例 2:
输入：nums = [1,2,3], k = 3
输出：2
🧩题目提示
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
🧪前缀和
❓什么是“前缀和”？
前缀和是一个技巧，用于快速计算数组任意一段区间 [i, j] 的和。
我们构造一个辅助数组 s，令：
s[i] 表示 nums[0] + nums[1] + ... + nums[i-1]
那么区间和 nums[i..j] 就可以表示为：
s[j+1] - s[i]
🤔 如何用前缀和优化“和为 k 的子数组”问题？
关键点在于变换等式：
s[j+1] - s[i] == k ⟺ s[i] == s[j+1] - k
换句话说，每次计算一个新的前缀和 s[j+1]，我们就可以检查之前有多少个前缀和等于 s[j+1] - k，那么这些位置开始的子数组就是合法的。
这个过程使用一个 unordered_map<int, int> 来实时记录每个前缀和的出现次数（频次），可以在 O(1) 时间内查询和更新。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> s(n + 1);
for(int i = 0;i < n;i++){
s[i + 1] = s[i] + nums[i];
}
int ans = 0;
unordered_map<int,int> cnt;
for(int i = 0;i < s.size();i++){
ans += cnt.contains(s[i] - k) ? cnt[s[i] - k] : 0;
cnt[s[i]]++;
}
return ans;
}
};
🌟 总结
前缀和（Prefix Sum） 是一种常见的预处理技巧，主要用于在 O(1) 时间内求任意子数组/区间的连续和。
前缀和本质是对数组进行一次扫描，将每个位置之前的累积值保存下来，方便后续快速计算区间和。
设原数组为 nums，构建前缀和数组 prefix（或 s），定义如下：
prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]
那么任意一个区间 [i, j] 的子数组和为：
sum(i..j) = prefix[j + 1] - prefix[i]
前缀和 = “先累加、后查找”，是快速处理连续区间求和问题的利器，尤其适用于带有“连续”、“区间”、“子数组”、“和为 K”、“模 K”等关键词的问题。
- 使用前缀和 + 哈希表可以高效统计和为 k 的子数组个数；
- 关键是理解：
s[j+1] - s[i] == k => s[i] = s[j+1] - k - 初始化
cnt[0] = 1是处理从头开始的子数组的必要手段。
🔚回顾前缀和知识整理（含差分）
✅ 一维前缀和
定义：
给定数组 a[1..n]，定义前缀和数组 s[i] = a[1] + a[2] + ... + a[i]
其中 s[0] = 0
求区间和 [l, r]：
int sum = s[r] - s[l - 1];
构建代码：
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
✅ 一维差分（前缀和的逆运算）
定义：
差分数组 d[i] = a[i] - a[i - 1]，可用于快速区间修改
区间加法操作：对区间 [l, r] 加 x
d[l] += x;
d[r + 1] -= x;
最终恢复原数组 a：
a[1] = d[1];
for (int i = 2; i <= n; i++) {
a[i] = a[i - 1] + d[i];
}
✅ 二维前缀和
定义：
给定二维数组 a[i][j]，定义二维前缀和 s[i][j] = a[1][1] + ... + a[i][j]
构建公式：
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
求子矩阵和 [(x1,y1), (x2,y2)]：
int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
✅ 二维差分
定义：
d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
对子矩阵 [(x1,y1), (x2,y2)] 加 x：
d[x1][y1] += x;
d[x2+1][y1] -= x;
d[x1][y2+1] -= x;
d[x2+1][y2+1] += x;
恢复原数组：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];
📌应用场景：
- 一维前缀和：快速求区间和
- 一维差分：快速区间加减
- 二维前缀和：求子矩阵和
- 二维差分：矩阵局部批量修改
