【优选算法篇】前缀之美,后缀之韵:于数列深处追寻算法的动与静
文章目录
- C++ 前缀和详解:进阶题解与思维分析
- 前言
- 第二章:前缀和进阶应用
- 2.1 和为 k 的子数组(medium)
- 解法一(前缀和 + 哈希表)
- 示例分析
- C++代码实现
- 易错点提示
- 代码解读
- 2.2 和可被 K 整除的子数组(medium)
- 解法(前缀和 + 哈希表 + 同余定理)
- 详细示例
- C++代码实现
- 易错点提示
- 代码解读
- 2.3 连续数组(medium)
- 解法(前缀和 + 哈希表)
- 示例分析
- C++代码实现
- 易错点提示
- 代码解读
- 2.4 矩阵区域和(medium)
- 解法(二维前缀和)
- 示例分析
- C++代码实现
- 易错点提示
- 代码解读
- 写在最后
C++ 前缀和详解:进阶题解与思维分析
💬 欢迎讨论:如有疑问或见解,欢迎在评论区留言互动。
👍 点赞、收藏与分享:如觉得这篇文章对您有帮助,请点赞、收藏并分享!
🚀 分享给更多人:欢迎分享给更多对 C++ 感兴趣的朋友,一起学习前缀和的基础与进阶!
前言
在前一篇文章中,我们讨论了前缀和的基本概念及其基础应用,展示了如何利用前缀和快速解决数组区间求和问题。在这篇文章中,我们将继续深入探讨前缀和的更多应用,尤其是在解决一些中级难度问题中的实用性和效率提升。
第二章:前缀和进阶应用
2.1 和为 k 的子数组(medium)
题目链接:560. 和为 K 的子数组
题目描述:
给你一个整数数组 nums
和一个整数 k
,请你统计并返回该数组中和为 k
的连续子数组的个数。
示例 1:
- 输入:
nums = [1,1,1], k = 2
- 输出:
2
- 解释:共有两个子数组的和为 2,分别是
[1,1]
和[1,1]
。
示例 2:
- 输入:
nums = [1,2,3], k = 3
- 输出:
2
- 解释:共有两个子数组的和为 3,分别是
[1,2]
和[3]
。
提示:
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7
解法一(前缀和 + 哈希表)
算法思路:
我们可以通过划分所有以 i
为结尾的子数组,逐步计算这些子数组的和是否为 k
。如果满足条件,则累加结果。
-
外层循环(枚举所有以
i
结尾的子数组):- 针对每一个位置
i
,我们寻找与其满足和为k
的连续子数组。
- 针对每一个位置
-
查找条件:
- 要使
t-i
的子数组和为k
,相当于找到位置0-t-1
的和为sum - k
。 - 通过累加
0-i
的前缀和sum[i]
,我们可以将此问题简化为查找sum[i] - k
是否在0-t-1
区间内存在。
- 要使
-
初始化
hash[0] = 1
:- 这里的
hash[0] = 1
是为了在t=0
时处理特殊情况。 - 假设
t=0
,即从数组的开始到i
位置的子数组和为k
,这等价于查找从0-t-1
的前缀和为0
。但t=0
时,区间0-t-1
为无效区间,因此初始化hash[0] = 1
可以保证从起点开始的累加和为k
。
- 这里的
示例分析
假设 nums = [1, 2, 3]
,k = 3
:
- 初始状态:
hash[0] = 1
- 遍历
nums
数组:- 第一次循环:
sum = 1
,在hash
中记录hash[1] = 1
- 第二次循环:
sum = 3
,此时sum - k = 0
存在于hash
,累积结果ret = 1
- 第三次循环:
sum = 6
,此时sum - k = 3
存在于hash
,累积结果ret = 2
- 第一次循环:
最终结果为 2
,即子数组 [1, 2]
和 [3]
满足和为 k
。
C++代码实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 记录前缀和出现的次数
hash[0] = 1; // 确保能统计到从起点到i的子数组和为k的情况
int sum = 0, ret = 0;
for(auto x : nums) {
sum += x; // 计算当前前缀和
if(hash.count(sum - k)) ret += hash[sum - k]; // 统计符合条件的前缀和个数
hash[sum]++; // 更新前缀和出现次数
}
return ret;
}
};
易错点提示
-
哈希表初始化:
hash[0] = 1
是关键,确保统计从数组起点到i
的子数组和为k
的情况。
-
前缀和更新顺序:
- 遍历过程中,计算
sum
后先查找hash[sum - k]
,再更新hash[sum]
。
- 遍历过程中,计算
-
返回值累加逻辑:
- 查询
hash[sum - k]
的值并累加至ret
,每次查找到的值直接反映了符合条件的子数组数量。
- 查询
代码解读
通过使用哈希表存储前缀和出现的次数,我们可以在一次遍历中快速找到和为 k
的子数组个数。
- 时间复杂度:
O(n)
,因为只需遍历数组一次。 - 空间复杂度:
O(n)
,最坏情况下,每个前缀和都唯一,存入哈希表。
2.2 和可被 K 整除的子数组(medium)
题目链接:974. 和可被 K 整除的子数组
题目描述:
给定一个整数数组 nums
和一个整数 k
,返回其中元素之和可被 k
整除的(连续、非空)子数组的数目。
示例 1:
- 输入:
nums = [4,5,0,-2,-3,1]
,k = 5
- 输出:
7
- 解释:共有 7 个子数组满足其元素之和可被
k = 5
整除:[4, 5, 0, -2, -3, 1]
,[5]
,[5, 0]
,[5, 0, -2, -3]
,[0]
,[0, -2, -3]
,[-2, -3]
示例 2:
- 输入:
nums = [5]
,k = 9
- 输出:
0
提示:
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
2 <= k <= 10^4
解法(前缀和 + 哈希表 + 同余定理)
算法思路:
目标是统计出和为 k
的倍数的子数组数量。通过利用前缀和和同余定理可以实现线性复杂度的解法:
-
同余定理:
两个数如果相减的差能够被k
整除,则它们的余数相同,即(a - b) % k == 0
等价于a % k == b % k
。
因此,只要在遍历过程中,当前位置前缀和与之前某个前缀和的余数相同,即可认为它们之间的子数组和能被k
整除。 -
前缀和与余数的关系:
- 用
sum[i]
表示从数组起始位置到i
的累加和。对于位置i
,要找到多少个以i
结尾且和可被k
整除的子数组,就需要查找在0
到i-1
区间内,前缀和对k
取余与sum[i] % k
相同的前缀和出现次数。
- 用
-
哈希表记录余数出现次数:
- 通过哈希表
hash
存储每种余数的出现次数,遍历时如果sum % k
在hash
中出现过,表示到当前位置i
存在相同余数的前缀和,可以形成满足条件的子数组。 - 每次找到余数相同的前缀和时,将其次数累加到结果中,然后更新
hash
。
- 通过哈希表
-
处理负数余数:
- 在某些编程语言中(如 C++),负数取模保留负号。为了避免负数影响判断,我们将余数调整为非负,表达式为
(sum % k + k) % k
。
- 在某些编程语言中(如 C++),负数取模保留负号。为了避免负数影响判断,我们将余数调整为非负,表达式为
详细示例
假设 nums = [4, 5, 0, -2, -3, 1]
,k = 5
:
-
初始状态:
hash[0] = 1
,表示从数组开始的和能被k
整除的情况。 -
遍历数组,逐步计算前缀和
sum
及其余数r = (sum % k + k) % k
,然后在hash
中查找相同余数出现次数并累加至结果中。- 第一次循环:
sum = 4
,r = 4
hash[4] = 1
更新
- 第二次循环:
sum = 9
,r = 4
hash[4]
已存在,累加结果ret += 1
- 更新
hash[4] = 2
- 第三次循环:
sum = 9
,r = 4
hash[4]
已存在,累加结果ret += 2
- 更新
hash[4] = 3
- 第四次循环:
sum = 7
,r = 2
hash[2] = 1
更新
- 第五次循环:
sum = 4
,r = 4
hash[4]
已存在,累加结果ret += 3
- 更新
hash[4] = 4
- 第六次循环:
sum = 5
,r = 0
hash[0]
已存在,累加结果ret += 1
- 更新
hash[0] = 2
- 第一次循环:
最终结果 ret = 7
,即共有 7 个子数组满足和能被 k
整除的条件。
C++代码实现
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 记录前缀和余数出现的次数
hash[0] = 1; // 确保能统计到从起点到i的子数组和为k的情况
int sum = 0, ret = 0;
for(auto x : nums) {
sum += x; // 计算当前位置的前缀和
int r = (sum % k + k) % k; // 修正后的余数
if(hash.count(r)) ret += hash[r]; // 统计符合条件的余数出现次数
hash[r]++; // 更新当前余数出现次数
}
return ret;
}
};
易错点提示
-
初始化
hash[0] = 1
:- 为了处理从数组起点到
i
的子数组和能被k
整除的情况,例如当sum[i] % k == 0
时,需要提前初始化hash[0] = 1
,否则初始状态无法统计正确的结果。
- 为了处理从数组起点到
-
负数取模的修正:
- 负数取模在 C++ 中保留负号。例如,
-1 % 5 = -1
。为了保证余数为非负,我们使用(sum % k + k) % k
表达式,确保余数始终落在[0, k-1]
范围。
- 负数取模在 C++ 中保留负号。例如,
-
返回值累加逻辑:
- 每次
sum % k
在哈希表中找到时,将其对应的次数累加到ret
中,即前缀和为i
的位置符合条件的子数组个数。
- 每次
代码解读
我们使用前缀和和同余定理,将问题简化为寻找具有相同余数的前缀和数量。在一次遍历中快速统计出满足条件的子数组数量。
- 时间复杂度:
O(n)
,因为只需遍历数组一次。 - 空间复杂度:
O(k)
,哈希表存储k
种余数
2.3 连续数组(medium)
题目链接:525. 连续数组
题目描述:
给定一个二进制数组 nums
,找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。
示例 1:
- 输入:
nums = [0,1]
输出:2
说明:[0, 1]
是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
- 输入:
nums = [0,1,0]
输出:2
说明:[0, 1]
(或[1, 0]
) 是具有相同数量 0 和 1 的最长连续子数组。
提示:
1 <= nums.length <= 10^5
nums[i]
不是 0 就是 1
解法(前缀和 + 哈希表)
算法思路:
- 将 0 视为 -1,1 视为 1,这样问题转化为寻找连续区间的和为 0。
- 使用前缀和来记录当前位置的和,目标是找到第一个与当前和相等的前缀和的位置,以便计算出最长子数组的长度。
-
初始化:
- 使用哈希表记录每种前缀和首次出现的位置。初始化时,将前缀和为 0 的位置设为 -1。
-
遍历数组:
- 计算当前的前缀和。如果该前缀和已存在于哈希表中,说明找到了一个和为 0 的区间,更新最长长度。
- 如果前缀和不存在于哈希表中,则将其加入哈希表,记录首次出现的位置。
示例分析
假设 nums = [0, 1, 0]
:
- 初始状态:
hash[0] = -1
- 遍历
nums
:- 第 0 次循环:
sum = -1
(0 转换为 -1),hash[-1] = -1
,首次出现,记录hash[-1] = 0
。 - 第 1 次循环:
sum = 0
,此时sum
已存在于hash
,计算ret = 1 - (-1) = 2
。 - 第 2 次循环:
sum = -1
,再次找到sum
已存在,计算ret = 2 - 0 = 2
。
- 第 0 次循环:
最终结果为 2
,即子数组 [0, 1]
或 [1, 0]
满足条件。
C++代码实现
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> hash;
hash[0] = -1; // 处理前缀和为 0 的情况
int sum = 0, ret = 0;
for (int i = 0; i < nums.size(); i++) {
sum += (nums[i] == 0) ? -1 : 1; // 将 0 视为 -1,1 视为 1
if (hash.count(sum))
ret = max(ret, i - hash[sum]); // 更新最大长度
else
hash[sum] = i; // 记录首次出现的位置
}
return ret;
}
};
易错点提示
-
哈希表初始化:
hash[0] = -1
确保能统计从起点到i
的子数组和为 0 的情况。
-
前缀和更新顺序:
- 在遍历过程中,计算
sum
后先查找hash[sum]
,再更新hash[sum]
。
- 在遍历过程中,计算
-
返回值累加逻辑:
- 计算长度时,利用哈希表中存储的前缀和位置来得到最长子数组的长度。
代码解读
通过使用哈希表存储前缀和出现的次数,我们可以在一次遍历中快速找到和为 0 的最长子数组的长度。
- 时间复杂度:
O(n)
,只需遍历数组一次。 - 空间复杂度:
O(n)
,最坏情况下,可能存储 n 个不同的前缀和。
2.4 矩阵区域和(medium)
题目链接:1314. 矩阵区域和
题目描述:
给你一个 m x n 的矩阵 mat
和一个整数 k
,请你返回一个矩阵 answer
,其中每个 answer[i][j]
是所有满足以下条件的元素 mat[r][c]
的和:
i - k <= r <= i + k
j - k <= c <= j + k
(r, c)
在矩阵内。
示例 1:
- 输入:
mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]
示例 2:
- 输入:
mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]
提示:
m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100
解法(二维前缀和)
算法思路:
- 使用二维前缀和的概念来高效计算每个
(i, j)
位置的矩阵区域和。 - 首先构造一个前缀和矩阵
dp
,然后根据区域的左上角和右下角的坐标来快速获取所需的和。
-
初始化前缀和矩阵:
- 构造一个
(m + 1) x (n + 1)
的前缀和矩阵dp
,其中dp[i][j]
表示mat
矩阵中(0,0)
到(i-1,j-1)
的元素和。
- 构造一个
-
计算前缀和:
- 遍历原矩阵
mat
,根据前缀和的性质填充dp
。
- 遍历原矩阵
-
计算区域和:
- 对于每个位置
(i, j)
,计算左上角和右下角的坐标,然后利用前缀和矩阵快速得到区域和。
- 对于每个位置
示例分析
假设 mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
,k = 1
:
-
初始化前缀和矩阵
dp
:- 计算出
dp
,其中dp[i][j]
是对应矩阵区域的和。
- 计算出
-
对于
i=1, j=1
位置:- 左上角坐标
(0, 0)
和右下角坐标(2, 2)
。 - 通过
dp
计算:ret[1][1] = dp[2][2] - dp[0][2] - dp[2][0] + dp[0][0]
。
- 左上角坐标
最终得到的矩阵区域和为 [[12, 21, 16], [27, 45, 33], [24, 39, 28]]
。
C++代码实现
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 1. 预处理前缀和矩阵
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
// 2. 计算区域和
vector<vector<int>> ret(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x1 = max(0, i - k), y1 = max(0, j - k);
int x2 = min(m - 1, i + k), y2 = min(n - 1, j + k);
ret[i][j] = dp[x2 + 1][y2 + 1] - dp[x1][y2 + 1] - dp[x2 + 1][y1] + dp[x1][y1];
}
}
return ret;
}
};
易错点提示
-
边界条件:
- 确保左上角和右下角的坐标在矩阵范围内,通过
max
和min
函数处理。
- 确保左上角和右下角的坐标在矩阵范围内,通过
-
前缀和更新:
- 在计算前缀和时,要注意从
(1,1)
开始填充,以避免越界。
- 在计算前缀和时,要注意从
-
结果计算逻辑:
- 注意在
dp
矩阵中使用的是x2 + 1
和y2 + 1
,因为dp
矩阵是多一行和多一列的。
- 注意在
代码解读
通过构建前缀和矩阵,可以在 O(1) 时间内计算任意区域的和,使得整个算法的时间复杂度为 O(m * n),而空间复杂度也是 O(m * n),适合给定的约束条件。
写在最后
前缀和作为一种高效的数据结构,极大地简化了众多数组与矩阵相关问题的求解过程。本文通过解析具体问题,如和为 k 的子数组、和可被 k 整除的子数组及最长连续数组,展示了前缀和与哈希表结合的威力。每个示例不仅提供了解法,还详细解释了代码实现的思路与易错点,帮助读者更好地理解与掌握。通过这些深入的分析,读者能够在面临复杂问题时,更自信地运用前缀和的技巧,提升解题效率。
以上就是关于【优选算法篇】前缀之美,后缀之韵:于数列深处追寻算法的动与静的内容啦,各位大佬有什么问题欢迎在评论区指正,您的支持是我创作的最大动力!❤️