这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作
目录
4.除自身以外数组的乘积
4.1解析
4.2题解
5.和为K的子数组
5.1解析
5.2题解
6.和可被K整除的子数组
6.1解析
6.2题解
7.连续数组
7.1题解
7.2题解
8.矩阵区域和
8.1解析
8.2题解
4.除自身以外数组的乘积
题目:. - 力扣（LeetCode）
4.1解析
这道题实际上和前一道"中心下标"的题目非常相似,只不过这道题要求的是"前缀积"和后缀积
那么我们用f来表示前缀积:
如图所示:f[i] 表示 i之前所有元素之积(不包括i元素),那么f[i] = f[i-1] * nums[i-1];
同理,如果我们用g 表示 i之后所有元素的积(不包括i元素),那么g[i] = g[i + 1] * nums[i+1]
其中有细节问题:
当i= 0时,是表示0之前所有元素之积,但是0之前没有元素了,我们前面是设0之前的元素为0,但是由于这道题是求积,那么应该设为1,即f[0] = g[n-1] = 1(n为数组长度)
在创建前缀和数组和后缀和数组后,我们仅需要遍历数组,计算f[i] * g[i]即可
4.2题解
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
f[0] = g[n-1] = 1;
for(int i = 1; i < n; i++){
f[i] = f[i-1] * nums[i-1];
}
for(int i = n-2; i >= 0; i--){
g[i] = g[i+1] * nums[i+1];
}
int[] ans = new int[n];
for(int i = 0; i < n; i++){
ans[i] = f[i] * g[i];
}
return ans;
}
}5.和为K的子数组
题目:. - 力扣（LeetCode）
5.1解析
看到"子数组"可能我们会想到利用双指针(滑动窗口)来做,但是实际上这道题利用滑动窗口是不行的
我们前面遇到的滑动窗口题目,left和right指针都是往同一个方向移动,但是由于这道题出现了0 和 负数,那么就会出现right往回走的情况,滑动窗口的优势就没有了
实际上我们应该想到的是前缀和的算法思想,但是前缀和记录的是从原点到某个位置的所有元素的和,但是我们要求的是某一段子区间.
类似这种题目,我们可以转变一下思路:
如图所示,我们可以通过计算i位置之前,满足sum[j] = sum[i] - k的点的个数,这样侧面求出来满足子区间元素和为k的个数
但是有几个细节问题:
(1) 我们怎么知道i前面满足条件的前缀和有几个?? 是从0位置开始遍历判断吗??很显然,这样做的时间复杂度将会不如暴力解法
我们可以利用哈希表来记录,某一个前缀和的值,以及出现的个数,这样但我们在判断i之前多少个前缀和满足 sum[j] = sum[i] - k时,只需要从hash表中直接拿值即可
(2)如果我们利用哈希表来存储,那么就会出现一个问题:
假设数组是上图这样的,k=0,那么显然 第一个 0 就可以作为满足情况的子数组之一,但是我们在遍历的时候是从第一个开始记录的,当记录第一个元素之前哈希表中是没有值的.因此我们需要先让哈希表里面有一个0的值,为1,即hash.put(0,1).这样,我们判断第一个数的时候,加入满足要求,就count++;
(3)既然我们不用重新回头遍历数组,那么实际上前缀和数组也没必要创建,因为都在哈希表中记录着,那么我们就仅需要设置一个变量记录当前的前缀和是多少即可
这么讲实际上有点抽象,我们通过代码来演示:
5.2题解
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int sum = 0, count = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
count += map.getOrDefault(sum-k,0);
map.put(sum,map.getOrDefault(sum,0)+1);
}
return count;
}
}6.和可被K整除的子数组
题目:. - 力扣（LeetCode）
6.1解析
要想做这道题,需要有两个前提知识点的补充:
(1)同余定理
如果(a - b) % == 0 ,那么a % p == b % p
(2)java 对于负数取余,符号是取决于左边数的正负.但是对于同余定理,这样的规则是不满足的,举个例子: (3 - (-2)) % 5 == 0,那么根据同余定理,就有 3 % 5 == -2 % 5,但是在java / c++很显然这样是不满足的.因此我们就要进行修正,就相当于我们如何让 3 % 5 == -2 % 5 在java中取余是成立的?? 我们可以这样操作: 让 a % p 后 假设 p,如 -2 % 5 + 5 就能得到3,但是这样正负不统一,因为正数 % 正数本来就是正数,不需要修正,修正了结果反而不对,我们只需在计算结果后面再 % p即可, 因此最后取余的表达式为:( a % p + p) % p
理解完上述的两个知识点后,我们回到这道题:
还是一样,由于出现了负数和 0 ,导致用滑动窗口算法不行的; 既然提到了子数组的和,我们不妨试试前缀和算法
和上一道题一样,前缀和记录的是从原点到某个位置的所有元素的和,但是我们要求的是某一段子区间.我们就可以利用前面讲到的方法转变一下思路:
我们要求的是满足(sum[i] - x) % k == 0的子区间的个数,这个式子不就是 同余定理左边的式子吗,那么就一定有 sum[i] % k == x % k,至于sum[i] 和 x就都是我们熟悉的前缀和了
我们就可以使用和上一题一样的方法来解决这道题,但是有一个注意事项
还是一样,假设我们第一个数就是满足条件的子数组,那么我们就要在第一个数前面找到一个子区间的元素和也能被k整除(实际上就是0),但是前面没有元素了,哈希表中没有存放任何值,那么这种情况就会漏掉.因此我们要在一开始就在哈希表中存放0这个值,即hash.put(0,1)
6.2题解
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer,Integer> hash = new HashMap<>();
int count = 0;
hash.put(0,1);
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
int r = (sum % k + k) % k;
count += hash.getOrDefault(r,0);
hash.put(r,hash.getOrDefault(r,0)+1);
}
return count;
}
}7.连续数组
题目:. - 力扣（LeetCode）
7.1题解
此题要我们找出最长一段子区间,满足区间中0 的个数和1的个数是一样的,那么这道题能不能使用滑动窗口去做呢?答案是不行的.因为数组中存在0,right指针是可能会回头的;那么我们转变一下思路,我们尝试把数组里面的0全部换成-1,那么当一段子区间的元素和为0的时候,就一定满足1的个数和0的个数一样,那么这样的话,我们就把问题转回求一段子区间的元素和为0的问题,那么就和我们前面的两道题一样
但是有几个细节问题:
1.这道题求的是最长的子区间,但是我们之前求的都是数量.因此这道题我们要改变哈希表的存储内容
假设我们遍历到i,那么这时候就要在前面找到一个子区间的长度也为sum,这时候就会出现两种情况
(1)哈希表里面没有sum,即在这之前的所有前缀和没有一个为sum的,这时候我们只需要将他存储在哈希表中即可,由于是要长度,那么我们哈希表的值就要存这个点的下标
(2)如果哈希表中存在,那么就要更新我们最终返回的长度,但是哈希表中的值是不需要修改的.因为我们要的是最长的子区间,那么我们在寻找的时候就要找最短前缀和,由于我们是从前往后遍历,那么此前如果存有sum,那么一定是最短的前缀和,此时对应子区间就最长
2.对于边界的处理
假设我们的数组是这样的,那么不难发现,整个数组就是满足条件的一种情况,按照我们前面的思路,那么这个时候就要在0下标之前找到一个前缀和为0的区间,但是实际上没有区间了,因此我们既要预处理,在下标为-1的位置存放前缀和为0的值
7.2题解
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer,Integer> hash = new HashMap<>();
int len = 0;
int sum = 0;
hash.put(0,-1);
for(int i = 0; i < nums.length; i++){
sum += nums[i] == 0 ? -1 : 1;//将所有的0变成-1
if(hash.containsKey(sum)){
len = Math.max(len,i-hash.get(sum));
}else{
hash.put(sum,i);
}
}
return len;
}
}8.矩阵区域和
题目:. - 力扣（LeetCode）
8.1解析
如图所示,题目实际上就是要求给定二维数组中,每个坐标从(i - k ,j-k) d到 (i+k,j+k)之间的元素之和,那么这不就是我们之前讲过的前缀和吗
(1)预处理dp数组
我们还是预处理一个dp数组,其中dp[i] [j]表示从原点到 (i,j)之间的元素之和.我们前面推导过:dp[i] [j] = dp[i-1] [j] + dp[i] [j - 1] + arr[i] [j] - dp[i-1] [j-1],但是注意:我们前面推导这个公式的前提是arr数组的下标是从1开始的,但是这道题的数组是给定的,从0开始的,印象我们需要修改公式:dp[i] [j] = dp[i-1] [j] + dp[i] [j - 1] + arr[i-1] [j-1] - dp[i-1] [j-1],那么我们就可以利用这个公式对dp数组进行初始化
(2)使用dp数组
接下来我们就要使用dp数组,我们也推导过.计算计算(x1, y1) ~ (x2, y2)的元素和的公式为:dp[x2] [y2] - dp[x1-1] [y2] - dp[x2] [y1 -1] + dp[x1-1] [y1-1],当我们创建一个返回数组ret的时候,那么ret[i] [j] 就是 (i - k ,j-k) d到 (i+k,j+k),但是要注意边界条件,即小于0的范围我们是当成0处理的,同样大于n-1的也是一样,那么我们的范围就需要改成:(max(i - k,0) , max(j-k,0) ) ~ (min(i + k,n-1) , min(j+k,n-1) );这样我们就直接省去了超出范围的情况
(3)下标映射关系
最后还有一个细节问题,就是ret数组和dp数组的下标映射关系,由于我们dp数组的下标是从1开始的,但是我们返回的ret数组的下标必须是从0开始的,因此实际上我们dp数组的下标是比ret数组的下标大1的,即在dp上的(i,j)实际上对应ret数组上的是(i-1,j-1)
8.2题解
public int[][] matrixBlockSum(int[][] mat, int k) {
int n = mat.length;
int m = mat[0].length;
int[][] dp = new int[n+1][m+1];
int[][] ret = new int[n][m];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] + 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 = Math.max(i-k,0)+1, y1 = Math.max(j-k,0)+1;
int x2 = Math.min(i+k,n-1)+1, y2 = Math.min(j+k,m-1)+1;
ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
}
}
return ret;
}
