网站怎么架设,住房建设厅网站,电影网站推广,承德市住房和城乡建设局网站前缀和 一、一维前缀和示例模板[寻找数组的中心下标 ](https://leetcode.cn/problems/tvdfij/description/)除自身以外的数组乘积和可被k整除的子数组 一、一维前缀和
前缀和就是快速求出数组某一个连续区间内所有元素的和。
示例模板
已知一个数组arr#xff0c;求前缀和 … 前缀和 一、一维前缀和示例模板[寻找数组的中心下标 ](https://leetcode.cn/problems/tvdfij/description/)除自身以外的数组乘积和可被k整除的子数组 一、一维前缀和
前缀和就是快速求出数组某一个连续区间内所有元素的和。
示例模板
已知一个数组arr求前缀和 第一步预处理一个前缀和数组dp,dp[i]表示从[1,i]区间内所有元素和。 dp[1]arr[1]; dp[2]arr[1]arr[2]dp[1]arr[2] dp[3]arr[1]arr[2]arr[3]dp[2]arr[3] … 以此类推可得dp[i]dp[i-1]arr[i] 第二步使用前缀和数组 假若区间【l,r】内所有元素和。可得dp[r]-dp[l-1]. 相应代码
for(int i1;in;i)
{dp[i]dp[i-1]arr[i];
}细节下表为什么从1开始假设求【03】区间和那么dp[3]-dp[-1],dp[-1]边界直接越界了.房主边界问题。 上述代码只是个参考具体问题应具体分析。 例题1
寻找数组的中心下标 解析 还是使用前缀和的思维。使用俩数组分别来记录中心下标左边的和以及右边的和。 然后遍历整个数组如果俩数组相等返回下标i class Solution {
public:int pivotIndex(vectorint nums) {int nnums.size();vectorintf(n),g(n);//处理前缀和 后缀和for(int i1;in;i)f[i]f[i-1]nums[i-1];for(int in-2;i0;i--)g[i]g[i1]nums[i1];for(int i0;in;i){if(f[i]g[i])return i;}return -1;}
}; 例题2
除自身以外的数组乘积
题目描述 给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法且在 O(n) 时间复杂度内完成此题。 解析这里使用的方法和上一道题解法类似只不过换了一种说法。题目所说求除i为之外其余元素的积我们换一种思维就是 前缀积和后缀积的积。假设我们要求i位置的值时我们可以求出【0,i-1】位置区间所有元素积和【i1,n-1】区间范围所有元素积。再将他俩相乘即可。草图如下 代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int nnums.size();vectorintf(n),g(n);f[0]g[n-1]1;//初始化//注意这里for(int i1;in;i)f[i]f[i-1]*nums[i-1];for(int in-2;i0;i--)g[i]g[i1]*nums[i1];//使用vectorintans(n);for(int i0;in;i){ans[i]g[i]*f[i];}return ans;}
}; 例3
和可被k整除的子数组
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。
解析 这里先讲一下有关知识点同余定理 在c/java中负%正负为了让这个余数是正数给出了这样的方法修正a%pp,但是又不能确定a是正数还是负数为了统一(a%pp)%p,以后取模运算有负数时用这个方法。 在该题中求可被k整除的子数组个数我们用到前缀和哈希方法。在[0,i-1]区间内找到多少前缀和余数等于(sum%kk)%k.,余数存进哈希表。定义个哈希表第一个int代表前缀和的余数第二个代表个数。 代码
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,inthash;//存的是余数hash[0%k]1;//余数int sum0,res0;for(auto x:nums){sumx;//算出当前位置前缀和int y(sum%kk)%k;//求余数if(hash.count(y)) reshash[y];hash[y];//不要忘记将余数继续扔进哈希表里}return res;}
};希望读者喜欢 你们的支持是小编动力的源泉
