Welcome to 9ilk's Code World
(๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏: 算法Journey
本篇我们来赏析前缀和算法的进阶题目。
🏠 和可被K整除的子数组
📌 题目解析
和可被k整除的子数组
📌 算法原理
这道题与"和为K的子数组"其实是类似的,我们以i位置为结尾的子数组观察,如果能找到一段右边部分能被k整除,此时问题转化成在这段区间内找有多少个前缀和等于x使得sum[i] -x 能被k整除?
- 同余定理
如果 (a - b) % n == 0 ,那么我们可以得到⼀个结论: a % n == b % n 。⽤⽂字叙述就是,如果两个数相减的差能被 n 整除,那么这两个数对 n 取模的结果相同。
因此我们只需要找是否有x对k的余数等于sum对k的余数即可。
- 前缀和为负数的情况
以K=4为例子,求出某个前缀和为-1,-1%K应该为3,但有的编程语言-1%K = -1(不同编程语言对商的取整是不同的,有的向0取整,有的向负无穷取整).这里的-1应该要加上K,转正成3.这是因为-1和3分别模4结果看似不相等,但是3-(-1) = 4,4%4 == 0,所以前缀和-1和3其实是等价的,只是不同语言对%运算的处理不同。
---》修正:我们应该让正负统一,毕竟他们是等价的,即求余数(a%p + p)%p
问题转化为:在[ 0 , i - 1]区间内,找到有多少个前缀和的余数等于(sum%k+k)%k。
我们哈希表此时存的不是前缀和,而是求前缀和的余数!
参考代码:
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int sum = 0;int n = nums.size();unordered_map<int,int> hash;int count = 0;hash[0] = 1;//sum[i]恰好就是能被整除for(int i = 0 ; i < n;i++){sum += nums[i];int leftnum = (sum%k + k)%k;if(hash[leftnum]) count += hash[leftnum];hash[leftnum]++;}return count;}};
🏠 连续数组
📌 题目解析
连续数组
- 数组中的数字不是0就是1。
📌 算法原理
本题也是能很好地转化,如果我们将所有的0转化为-1,此时问题转化为在数组中找最长的子数组,使子数组中所有元素为0(和为0的子数组)。
- 由于涉及最长的子数组,哈希表里应该存的是某个位置的前缀和和这个位置的下标。
- 使用完i位置之后,再将其丢进哈希表。
- 长度求法:i - j.
- 如果重复的<sum,i>,此时我们只需保留前面的那一对。(因为我们要最长的子数组,也就是要sum[i] - 0 = sum这个前缀和越短越好)
- 默认前缀和为0的情况,此时表示sum正好为0,我们需要在这段区间的左边找等于0的子数组,显然是不存在的,因此设置hash[0] = -1即可。
参考代码:
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; // 计算当前位置的前缀和if(hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum] = i;}return ret;}
};
🏠 矩阵区域和
📌 题目解析
矩阵的区域和
📌 算法原理
- 由于i - k <= r <= i + k 和 j - k <= c <= j + k,所以r和c都分别有最大值和最小值,问题转化为求某块区域的面积,可以用到我们的二维前缀和,具体可跳转至前缀和模板
- 由于i-k和i+k/j-k和j+k可能超出行数和列数,所以当超过时,我们应该取二维的边界。
参考代码:
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {//int n = mat.size();int m = mat[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));vector<vector<int>> answer(n, vector<int>(m));//获得二维前缀和数组for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = dp[i][j - 1] + dp[i - 1][j] + mat[i - 1][j - 1] - dp[i - 1][j - 1];}}//使用前缀和数组for (int i = 0; i < n; i++){for (int j = 0; j < m; j++) { //确定下标int x1 = ((i - k) < 0) ? 0 : i - k;int x2 = (i + k >= n) ? n - 1 : i + k;int y1 = (j - k < 0) ? 0 : j - k;int y2 = (j + k >= m) ? m - 1 : j + k;answer[i][j] = dp[x2 + 1][y2 + 1] - dp[x2 + 1][y1] - dp[x1][y2 + 1] + dp[x1][y1];}}return answer;}
};
通过这几道题我们可以发现,在做前缀和题目我们当要求一段连续区间(比如子数组)可以想到用前缀和,此时需要进行适当的转化。