电子商务网站怎么做,wordpress 表格,wordpress4.7.5下载,营销类网站建设需要注意的问题前缀和是什么#xff1a; 前缀和指一个数组的某下标之前的所有数组元素的和#xff08;包含其自身#xff09;。前缀和分为一维前缀和#xff0c;以及二维前缀和。前缀和是一种重要的预处理#xff0c;能够降低算法的时间复杂度
说个人话就是比如有一个数组#xff1a; …
前缀和是什么 前缀和指一个数组的某下标之前的所有数组元素的和包含其自身。前缀和分为一维前缀和以及二维前缀和。前缀和是一种重要的预处理能够降低算法的时间复杂度
说个人话就是比如有一个数组 [1,2,3,4]然后我求得sum数组[1,3,6,10]; 那我只要有了这个sum数组我就可以在O1得时间内求出区间和 比如我想求interval[i,j]内得区间和我怎么办我直接那sum[j]-sum[i]就可以了。
ok了解了这个思想我们也很容易想到前缀和得作用或者说前缀和适合解决什么样的题目呢就是子数组或者字字符串类似的题目 下面上例题先从简单的开始
leetcode1732找到最高海拔
有一个自行车手打算进行一场公路骑行这条路线总共由 n 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain 其中 gain[i] 是点 i 和点 i 1 的 净海拔高度差0 i n。请你返回 最高点的海拔 。
有一个自行车手打算进行一场公路骑行这条路线总共由 n 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain 其中 gain[i] 是点 i 和点 i 1 的 净海拔高度差0 i n。请你返回 最高点的海拔 。
class Solution {public int largestAltitude(int[] gain) {int len gain.length;int[] sum new int[len1];for(int i1;ilen;i){sum[i] gain[i-1]sum[i-1];}int flag Integer.MIN_VALUE;for(int i0;ilen;i){if(sum[i]flag){flag sum[i];}}return flag;}
}
这道题也算是前缀和的一个入门我们求出前缀和数组sum之后遍历sum找到最大值即可。 leetcode 1413 逐步求和得到正数的最小值
给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。
你需要从左到右遍历 nums 数组并将 startValue 依次累加上 nums 数组中的值。
请你在确保累加和始终大于等于 1 的前提下选出一个最小的 正数 作为 startValue 。
输入nums [-3,2,-3,4,2]
输出5
解释如果你选择 startValue 4在第三次累加时和小于 1 。累加求和startValue 4 | startValue 5 | nums(4 -3 ) 1 | (5 -3 ) 2 | -3(1 2 ) 3 | (2 2 ) 4 | 2(3 -3 ) 0 | (4 -3 ) 1 | -3(0 4 ) 4 | (1 4 ) 5 | 4(4 2 ) 6 | (5 2 ) 7 | 2class Solution {public int minStartValue(int[] nums) {int len nums.length;int[] sum new int[len1];for (int i 1; i len; i) {sum[i] sum[i-1]nums[i-1];}int flag Integer.MAX_VALUE;for (int i 1; i len ; i) {if(sum[i]flag){flag sum[i];}}return flag0?(flag*-1)1:1;}
}
这道题就比上一道需要多分析一些东西
首先题目要求一个最小的正整数所以我们肯定要根据这个数组的和来求。
leetcode 724找数组的中心下标 给你一个整数数组 nums 请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。
那这道题目不是典型的前缀和嘛我们要求这个所谓的中心下标我们不就是这个中心下标的左边的区间和右边的区间和嘛
public int pivotIndex(int[] nums) {int len nums.length;int i;int[] sum new int[len 1];sum[0] 0;for (i 0; i len; i) {sum[i 1] sum[i] nums[i];}for (i 1; i len1; i) {if (sum[len] (2 * sum[i - 1]) nums[i-1]) {return i-1;}}return -1;} 当我们算出来这个sum数组之后我们只需要从左往右遍历一下然后根据数学公式就可以得出下标的结果 这里有一个注意点 就是你求sum数组的时候你需要在sum[0]的位置垫一个0这也是前缀和的固定套路怎么理解呢 比如有一个数组[1,0,0,0],那这个时候1这个位置很明显是中心坐标如果你不垫个0在前面的话公式就不成立 其实这种情况也可以作为一个特判我认为也可以理解为一个前缀和的固定套路。 线性前缀和变形
leetcode 238 除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。
输入: nums [1,2,3,4]
输出: [24,12,8,6]
先写一种比较容易想到的方法
利用对应索引的左侧和右侧也可以叫前缀和后缀的乘积来得出答案
举个例子[1,2,3,4]
我们先算出这个数组的前缀和数组和后缀和数组
[1,2,6,24] [24,24,12,4]
比如我们要求2这个下标的除自身以外数组的乘积
我们就可以用前缀和数组的第一个元素1和后缀和数组的倒二个元素12相乘得出12。
class Solution {public int[] productExceptSelf(int[] nums) {int len nums.length;int[] left new int[len];left[0] nums[0];int[] right new int[len];right[len-1] nums[len-1];for(int i1;ilen;i){left[i] nums[i]*left[i-1];}for(int ilen-2;i0;i--){right[i] nums[i]*right[i1];}int[] ans new int[len];ans[0] right[1];ans[len-1] left[len-2];for(int i1;ilen-1;i){ans[i] left[i-1]*right[i1];}return ans;}
} 再来一种难一点的方法
思路就是
先从上往下算对应索引的左变得乘积然后再倒上去算对应所以右边得乘积。
类似有点像上三角和下三角得感觉。
//假如nums为[1,2,3,4]那么answer的值分别为[(2,3,4),(1,3,4),(1,2,4),(1,2,3)]//如果吧i当前值相乘的时候看做是1那么就有如下样式// 1, 2, 3, 4 // 1, 1, 3, 4// 1, 2, 1, 4// 1, 2, 3, 1// 他的对角线1将他们分割成了两个三角形对于answer的元素//我们可以先计算一个三角形每行的乘积然后再去计算另外一个三角形每行的乘积//然后各行相乘就是answer每个对应的元素
class Solution {public int[] productExceptSelf(int[] nums) {int len nums.length;int[] left new int[len];left[0] 1;for(int i1;ilen;i){left[i] nums[i-1]*left[i-1];}int temp 1;for(int ilen-1;i0;i--){left[i] left[i]*temp;temp * nums[i];}return left;}
} leetcode 1310子数组异或查询
有一个正整数数组 arr现给你一个对应的查询数组 queries其中 queries[i] [Li, Ri]。
对于每个查询 i请你计算从 Li 到 Ri 的 XOR 值即 arr[Li] xor arr[Li1] xor ... xor arr[Ri]作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
输入arr [1,3,4,8], queries [[0,1],[1,2],[0,3],[3,3]]
输出[2,7,14,8]
解释
数组中元素的二进制表示形式是
1 0001
3 0011
4 0100
8 1000
查询的 XOR 值为
[0,1] 1 xor 3 2
[1,2] 3 xor 4 7
[0,3] 1 xor 3 xor 4 xor 8 14
[3,3] 8这道题其实蛮简单不知道为什么力扣设置成中等题
这道题有一个小的注意点这道题的前缀和数组的第一个元素应该是多少
这就要去考虑异或的性质了。 两个数异或相同的位数等于0 0110 ^ 1100 1010一个数与0异或结果等于本身一个数异或本身结果为0综上可得第四条性质 a ^ b ^ b a;
所以由异或性质得出前缀和数组的第一个数应该是0。
class Solution {public int[] xorQueries(int[] arr, int[][] queries) {int[] xor new int[arr.length1];for (int i 1; i arr.length; i) {xor[i] xor[i-1] ^ arr[i-1];}int[] ans new int[queries.length];for (int i 0; i queries.length; i) {ans[i] xor[queries[i][1]1] ^ xor[queries[i][0]];}return ans;}
}
leetcode 1829每个查询的最大异或值
给你一个 有序 数组 nums 它由 n 个非负整数组成同时给你一个整数 maximumBit 。你需要执行以下查询 n 次
找到一个非负整数 k 2的maximumBit次方 使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。从当前数组 nums 删除 最后 一个元素。
请你返回一个数组 answer 其中 answer[i]是第 i 个查询的结果。
输入nums [0,1,1,3], maximumBit 2
输出[0,3,2,3]
解释查询的答案如下
第一个查询nums [0,1,1,3]k 0因为 0 XOR 1 XOR 1 XOR 3 XOR 0 3 。
第二个查询nums [0,1,1]k 3因为 0 XOR 1 XOR 1 XOR 3 3 。
第三个查询nums [0,1]k 2因为 0 XOR 1 XOR 2 3 。
第四个查询nums [0]k 3因为 0 XOR 3 3 。这道题和上一道题差不多都是异或类型的前缀和
这一题需要多考虑的一个条件就是这个k的大小题目说k小于2的maximumBit次方我们由异或的性质可以知道我们要想最后的结果尽可能大我们希望我们异或的对象的1尽可能的多。
知道这个条件之后这题就很简单了我们只需要把我们累异或的结果都和这个最大值进行异或就行。
class Solution {public int[] getMaximumXor(int[] nums, int maximumBit) {int flag (1 maximumBit) - 1;int[] ans new int[nums.length];int k 0;for(int i0;inums.length;i){k ^ nums[i];ans[nums.length-1-i] flag ^ k;}return ans;}
}
线性前缀和统计
leetcode 523:连续的子数组和
给你一个整数数组 nums 和一个整数 k 编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组
子数组大小 至少为 2 且子数组元素总和为 k 的倍数。
如果存在返回 true 否则返回 false 。
如果存在一个整数 n 令整数 x 符合 x n * k 则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数
输入nums [23,2,4,6,7], k 6
输出true
解释[2,4] 是一个大小为 2 的子数组并且和为 6 。
先贴一个我一开始写的超时解法
class Solution {public boolean checkSubarraySum(int[] nums, int k) {int[] sum new int[nums.length1];int i,j;if(nums.length1){return false;}if(nums.length2){int temp nums[0]nums[1];return temp%k0?true:false;}for(i1;inums.length;i){sum[i] nums[i-1] sum[i-1];}for(i0;i nums.length-1;i){for(j(i2);j nums.length;j){if((sum[j]-sum[i])%k0){return true;}}}return false;}
}
很明显这是一个n方的解法。
下面贴正确解法
首先在做这个题目之前我们需要去明白一个数学关系
预处理前缀和数组 sum方便快速求得某一段区间的和。然后假定 [i,j] 是我们的目标区间那么有
sum[j]−sum[i−1]n∗ksum[j] - sum[i - 1] n * k sum[j]−sum[i−1]n∗k 经过简单的变形可得
sum[j]/k - sum[i-1]/k n
要使得两者除 k 相减为整数需要满足 sum[j] 和 sum[i−1]对 k取余相同。
这个就是我看题解看到的数学关系下面是证明 知道了这一层数学关系之后我们的思路就变成了
先开一个哈希表。
我们从前缀和数组i2的情况开始遍历我们把sum[i-2]%k的这个余数存在哈希表中
我们每次遍历一个元素就去查这个哈希表中是否有和我们这个余数相同的数。
这其实和经典题目两数之和有点像了。
class Solution {public boolean checkSubarraySum(int[] nums, int k) {int len nums.length;int[] sum new int[len1];SetInteger table new HashSet();for(int i1;ilen;i){sum[i] sum[i-1] nums[i-1];}int flag 0;for(int i2;ilen;i){flag sum[i-2]%k;table.add(flag);if(table.contains(sum[i]%k)){return true;}}return false;}
}
leetcode 1508:子数组和排序后的区间和
给你一个数组 nums 它包含 n 个正整数。你需要计算所有非空连续子数组的和并将它们按升序排序得到一个新的包含 n * (n 1) / 2 个数字的数组。
请你返回在新数组中下标为 left 到 right 下标从 1 开始的所有数字和包括左右端点。由于答案可能很大请你将它对 10^9 7 取模后返回。
输入nums [1,2,3,4], n 4, left 1, right 5
输出13
解释所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le 1 到 ri 5 的和为 1 2 3 3 4 13 。
这题其实没有什么技巧就是一道前缀和的模拟题我们先求一下前缀和数组然后开一个长度为n * (n 1) / 2 个数字的数组对前缀和数组遍历把每个子数组的和给求出来然后排序最后输出即可。
class Solution {int mod 1000000007;public int rangeSum(int[] nums, int n, int left, int right) {int[] sum new int[n1];int i,j;for(i1;in;i){sum[i] sum[i-1] nums[i-1];}int[] ans new int[(n*(n1))/2];int index 0;for(i1;in;i){for(ji;jn;j){ans[index] sum[j] - sum[i-1];}}Arrays.sort(ans);int result 0;for(ileft-1;iright;i){result ans[i];result result%mod;}return result;}
}
这里说一个小坑
就是最后这个result数据的处理
我一开始是 Arrays.sort(ans);int result 0;for(ileft-1;iright;i){result ans[i]%mod;}return result;
这样写有什么问题呢那个ans[i]会先做取余操作然后再 就会导致后面的结果溢出。
改成 result result ans[i] )%mod 和 result ans[i]; result result%mod;都行。 leetcode 1423可连续的最大点数
几张卡牌 排成一行每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动你可以从行的开头或者末尾拿一张卡牌最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k请你返回可以获得的最大点数。
输入cardPoints [1,2,3,4,5,6,1], k 3
输出12
解释第一次行动不管拿哪张牌你的点数总是 1 。但是先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌最终点数为 1 6 5 12 。
思路
这题应该怎么想呢或者说我们怎么往前缀和那个方面想呢
我们知道前缀和解决的是连续子数组或者子字符串的问题我们再看这个题目题目说我们抽牌可以从前面抽也可以从后面抽那这个数组就不一定是连续的了
这个时候我们就需要逆向思维一下。
我们想要抽出来的牌最大那就是剩下的牌最小我们抽牌的数组不一定连续不过剩下来的数组一定是连续的所以我们的思路就是去求剩下来的牌的最小值。
具体来说
我们要抽k张牌就是要剩下len-k张牌所以我们可以维护一个len-k张牌的滑动窗口。
我们一开始直接把这个滑动窗口填满然后再开始遍历这个数组不断更新这个连续子数组的最小值即可。 这里说一个题外话为什么要先填满滑动窗口其实我一开始的做法不是先填满是遍历完了len-k个元素之后再遍历剩下的元素不过我感觉这样下标处理起来好麻烦。 class Solution {public int maxScore(int[] cardPoints, int k) {int len cardPoints.length;int[] sum new int[len1];int i,cur 0,min Integer.MAX_VALUE;int flag len-k;for(i1;ilen;i){sum[i] cardPoints[i-1] sum[i-1];}for(i0;iflag;i){cur cardPoints[i];}for(iflag;ilen;i){cur Math.min(cur,sum[i]-sum[i-flag]);}return sum[len]-cur;}
}
leetcode 1685:有序数值中差绝对值之和
给你一个 非递减 有序整数数组 nums 。
请你建立并返回一个整数数组 result它跟 nums 长度相同且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。
换句话说 result[i] 等于 sum(|nums[i]-nums[j]|) 其中 0 j nums.length 且 j ! i 下标从 0 开始。
输入nums [2,3,5]
输出[4,3,5]
解释假设数组下标从 0 开始那么
result[0] |2-2| |2-3| |2-5| 0 1 3 4
result[1] |3-2| |3-3| |3-5| 1 0 2 3
result[2] |5-2| |5-3| |5-5| 3 2 0 5。
思路
根据这个例子很容易想到我们可以一种解法
比如我们要找nums[i]3这个情况下的result我们可以用nums[i]*len - sum[len-1]
代码
class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int sum 0;int i;for(i0;i nums.length;i){sum nums[i];}int[] result new int[nums.length];for(i0;i nums.length;i){result[i] Math.abs((nums[i]* nums.length)-sum);}return result;}
}
我们很快就会发现是错误的因为这题算的是绝对值
按原来的算法我们用nums[i]*len - sum[len-1] 得出3*3-10然后取绝对值
这样算出来的值是1不过答案是3问题就是3-2是0的而3-5是分开取绝对值的和是3而我们直接把这两个数合在一起算了。
解决办法是
我们观察到这个数组是有序的所以我们可以分段进行求并且利用前缀和数组进行优化
class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int[] sum new int[nums.length];int len nums.length;int i,j;sum[0] nums[0];for(i1;i nums.length;i){sum[i] sum[i-1] nums[i];}int[] result new int[len];for(i0;ilen;i){result[i] ((i1)*nums[i]-sum[i]) (sum[len-1]-sum[i]-(len-i-1)*nums[i]);}return result;}
}
leetcode 2155:分组得分最高的所有下标
给你一个下标从 0 开始的二进制数组 nums 数组长度为 n 。nums 可以按下标 i 0 i n 拆分成两个数组可能为空numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素包括 0 和 i - 1 而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素包括 i 和 n - 1 。如果 i 0 numsleft 为 空 而 numsright 将包含 nums 中的所有元素。如果 i n numsleft 将包含 nums 中的所有元素而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
输入nums [0,0,1,0]
输出[2,4]
解释按下标分组
- 0 numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 1 1 。
- 1 numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 1 2 。
- 2 numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 1 3 。
- 3 numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 0 2 。
- 4 numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 0 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意答案 [4,2] 也被视为正确答案。思路
我一开始想的思路是求出前缀和数组因为这个数组中只有0和1所以我们只要有了前缀和数组我们可以通过下标的关系很快得出0和1的个数也就是这个时候的分数。
class Solution {public ListInteger maxScoreIndices(int[] nums) {int len nums.length;int[] sum new int[len1];for(int i1;ilen;i){sum[i] sum[i-1] nums[i-1];}ListInteger ans new ArrayList();int score -1;ans.add(score);int temp 0;for(int i0;ilen;i){temp Math.abs(sum[i]-(i1)) sum[len] - sum[i];if(tempscore){ans.clear();ans.add(i);score temp;} else if (tempscore) {ans.add(i);}}return ans;}
}
更好的思路
这里其实可以利用到一点贪心的想法我们要想让这个分数尽可能大其实就让左半边尽可能有多的0。
class Solution {public ListInteger maxScoreIndices(int[] nums) {int len nums.length;int maxscore 0;int preSum 0;ListInteger ans new ArrayList();ans.add(0);for(int i0;ilen;i){if(nums[i]0){preSum;if(preSummaxscore){ans.clear();ans.add(i1);maxscore preSum;} else if (preSummaxscore) {ans.add(i1);}}else preSum--;}return ans;}
} 这里有一个小细节就是我们要在列表之前先垫一个0我们可以想象[1,1]这个数组里面没有一个0如果我们不垫这个0答案就什么都没有。 leetcode 2222 选择建筑的方案数
给你一个下标从 0 开始的二进制字符串 s 它表示一条街沿途的建筑类型其中
s[i] 0 表示第 i 栋建筑是一栋办公楼s[i] 1 表示第 i 栋建筑是一间餐厅。
作为市政厅的官员你需要随机 选择 3 栋建筑。然而为了确保多样性选出来的 3 栋建筑 相邻 的两栋不能是同一类型。
比方说给你 s 001101 我们不能选择第 1 3 和 5 栋建筑因为得到的子序列是 011 有相邻两栋建筑是同一类型所以 不合 题意。
请你返回可以选择 3 栋建筑的 有效方案数 。
输入s 001101
输出6
解释
以下下标集合是合法的
- [0,2,4] 从 001101 得到 010
- [0,3,4] 从 001101 得到 010
- [1,2,4] 从 001101 得到 010
- [1,3,4] 从 001101 得到 010
- [2,4,5] 从 001101 得到 101
- [3,4,5] 从 001101 得到 101
没有别的合法选择所以总共有 6 种方法。
思路
这题和之前的前缀和题目有些不同这道题更多是用了前缀和的思想。 对任意一个位置以它为中心构建合法相邻建筑的数量分两种情况讨论 该位置左侧1的数量*该位置右侧1的数量 若该位置为0 。这样可以构成101。 该位置左侧0的数量*该位置右侧0的数量 若该位置为1 。这样可以构成010。 一般前缀和得前缀和数组求得是某一个位置元素前面得和。
这道题求的是某一个位置前面1或者0的数量。 具体算法思路
先从右往左遍历一次数组算出对应位置右侧0或者1的数量这个位置如果是0就算1的数量相反也一样再从左往右遍历一次数组算出对应位置的方案数因为我们这个时候已经有右侧对应的0和1的数量这个时候的zeroCount和oneCount分别对应左侧的0和1的数量我们直接相乘即可得出这个位置上的方案数
class Solution {public long numberOfWays(String s) {int len s.length();int[] count new int[len];char[] str s.toCharArray();long ans 0;int i;int oneCount 0;int zeroCount 0;//从右往左遍历统计每个位置右侧0或者1的数量for(ilen-1;i0;i--){if(str[i]0){count[i] oneCount;}else count[i] zeroCount;oneCount str[i]1?1:0;zeroCount str[i]0?1:0;}oneCount 0; zeroCount 0;//从左往右遍历根据count数组算出每个位置对应的方案数for(i0;ilen;i){if(str[i]0){count[i] * oneCount;}else count[i] * zeroCount;oneCount str[i]1?1:0;zeroCount str[i]0?1:0;ans count[i];}return ans;}
}
线性前缀和哈希表
在做这个专题的题目之前我觉得得先复习一下经典的一道题目两数之和
class Solution {public int[] twoSum(int[] nums, int target) {Map Integer,Integer table new HashMap();table.put(nums[0],0);for(int i1;inums.length;i){if(table.containsKey(target-nums[i])){int[] ans new int[2];ans[0] table.get(target-nums[i]);ans[1] i;return ans;}table.put(nums[i],i);}return new int[2];}
} 我感觉在做前缀和和哈希表的题目中总是有两数之和这道题目的影子 两数之和这道题用了哈希表求在一个集合中是否有我们需要的目标值。 而在做前缀和的题目中用哈希表更像是在集合中找我们需要的区间段。 因为我们知道前缀和就是用来解决子数组的问题 下面上例题
leetcode 930. 和相同的二元子数组
给你一个二元数组 nums 和一个整数 goal 请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
输入nums [1,0,1,0,1], goal 2
输出4
解释
有 4 个满足题目要求的子数组[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
class Solution {public int numSubarraysWithSum(int[] nums, int t) {int len nums.length;MapInteger,Integer map new HashMap();map.put(0,1);int[] sum new int[len1];int i,j;int ans 0;for(i1;ilen;i){sum[i] sum[i-1] nums[i-1];}for(i0;ilen;i){int tar sum[i1] - t;if(map.containsKey(tar)){ans map.get(tar);}map.put(sum[i1],map.getOrDefault(sum[i1],0)1);}return ans;}
} 两数之和中的哈希表存储的是数组的值和索引
而这道题存储的是前缀和数组的值和出现的次数
leetcode560 和为K的子数组
class Solution {public int subarraySum(int[] nums, int k) {if (nums.length 0) {return 0;}HashMapInteger,Integer map new HashMap();//细节这里需要预存前缀和为 0 的情况会漏掉前几位就满足的情况//例如输入[1,1,0]k 2 如果没有这行代码则会返回0,漏掉了112和1102的情况//输入[3,1,1,0] k 2时则不会漏掉//因为presum[3] - presum[0]表示前面 3 位的和所以需要map.put(0,1),垫下底map.put(0, 1);int count 0;int presum 0;for (int x : nums) {presum x;//当前前缀和已知判断是否含有 presum - k的前缀和那么我们就知道某一区间的和为 k 了。if (map.containsKey(presum - k)) {count map.get(presum - k);//获取次数}//更新map.put(presum,map.getOrDefault(presum,0) 1);}return count;}
} 这道题就和上一道几乎一模一样哈希表的存储的都是前缀和数组的值和出现的次数。
leetcode 1248统计优美子数组
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
输入nums [1,1,2,1,1], k 3
输出2
解释包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
这道题其实没有用到前缀和数组不过用到了前缀和的思想。
前缀和数组表示数组下标之前的数组元素的和
这道题用了前缀和的思想我们不是去统计数组元素的和
而是统计数组下标之前的奇数数字的个数。 做完这道题之后我感觉对前缀和思想的理解深入了一点之前有一道题leetcode2222也用了前缀和的思想这道题统计的是数组下标之前0或者1元素的个数。那个时候理解起来好别扭可能是对这个前缀和数组的理解不对认为做这种题目都需要去求这个前缀和数组。 class Solution {public int numberOfSubarrays(int[] nums, int k) {int len nums.length;HashMapInteger,Integer map new HashMap();//哈希表记录的是前缀区间中的奇数个数map.put(0,1);int ans 0;int oddnum 0;int i,j;for(i0;ilen;i){oddnum nums[i] 1;if(map.containsKey(oddnum-k)){ans map.get(oddnum-k);}map.put(oddnum,map.getOrDefault(oddnum,0)1);}return ans;}
} leetcode 974和可被K整除的子数组
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。
输入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]
其实写了三个题目了已经就是有感觉了这道题和前几道题有什么不同呢特别是和为K的子数组
在和为K的子数组中我们的判断条件是是否含有sum[i] - k的前缀和
而在这一题中我们的判断条件是是否含有sum[i] %k相同的前缀和。
知道了这一点之后这题就和之前的题目差不多了。
class Solution {public int subarraysDivByK(int[] nums, int k) {int len nums.length;HashMapInteger,Integer map new HashMap();map.put(0,1);int i,j;int ans 0;int[] sum new int[len1];for(i1;ilen;i){sum[i] sum[i-1] nums[i-1];}for(i0;ilen;i){int key (sum[i1] % k k) % k;if(map.containsKey(key)){ans map.get(key);}map.put(key,map.getOrDefault(key,0)1);}return ans;}
} 注意点 我们看到上面代码中有一段代码是这样的 int key (presum % K K) % K; 这是为什么呢不能直接用 presum % k 吗 这是因为当我们 presum 为负数时需要对其纠正。纠正前(-1) %2 (-1)纠正之后 ( (-1) % 2 2) % 21 保存在哈希表中的则为 1.则不会漏掉部分情况例如输入为 [-1,2,9],K 2如果不对其纠正则会漏掉区间 [2] 此时 2 % 2 0符合条件但是不会被计数。 我觉得这个取余的方法也可以记下来用来处理一些碰到负数取余的情况。
差分
差分可以看成前缀和的逆运算
详细差分算法理解看这个博客前缀和与差分 图文并茂 超详细整理全网最通俗易懂-CSDN博客
我们稍微对比一下前缀和和差分的例子来理解一下这两个概念
前缀和的作用很清楚了
如果我们要求一个数组中某一段区间的数组和我们用前缀和就可以在O1的时间内查找出来。
而差分呢
我们想象一个场景我们有一个数组我们要在规定的区间 [l,r] 这个区间内c 我们同样得遍历如果我们需要做n次这样的操作那时间复杂度就很高了。
所以差分数组就是用来解决这个问题的。 对 c[l]v由于差分是前缀和的逆向过程这个操作对于将来的查询而言带来的影响是对于所有的下标大于等于 l 的位置都增加了值 v 对 c[r1]−v由于我们期望只对 [l,r] 产生影响因此需要对下标大于 r 的位置进行减值操作从而抵消“影响”。 最后我们再用前缀和的运算来输出结果即可。
leetcode 1109 航班预定统计
这里有 n 个航班它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings 表中第 i 条预订记录 bookings[i] [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti 包含 firsti 和 lasti 的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer里面的元素是每个航班预定的座位总数。
输入bookings [[1,2,10],[2,3,20],[2,5,25]], n 5
输出[10,55,45,25,25]
解释
航班编号 1 2 3 4 5
预订记录 1 10 10
预订记录 2 20 20
预订记录 3 25 25 25 25
总座位数 10 55 45 25 25
因此answer [10,55,45,25,25]
这道题就是典型的差分题
我们遍历bookings数组对数组中[l,r]区间加上对应的位置。
在rlen再减去对应的位置达到平衡。
最后求出前缀和。
class Solution {public int[] corpFlightBookings(int[][] bs, int n) {int[] diff new int[n2];for(int[] b:bs){diff[b[0]] b[2];diff[b[1]1] - b[2];}int[] ans new int[n];ans[0] diff[1];for(int i1;in;i){ans[i] ans[i-1]diff[i1];}return ans;}
}
