目录1.前缀和2.二维前缀和3.寻找数组的中心下标4.除了自身以外数组的乘积5.和为K的子数组6.和可被K惩处的子数组7.连续数组1.前缀和【模板】前缀和_牛客题霸_牛客网这道题看着题目内容很多其实就是给出一个指定数组然后每次查询这个数组的某一段区间之和是多少这道题就是前缀和算法的基础毕竟题目都直接写明了前缀和嘛那么我们就可以根据原数组创建出一个前缀和数组对于第i个位置存储从1~i位置所有元素的和因为这里元素下标从1开始所以注意创建数组要多开一个位置这里假设我们创建了一个num原数组和f前缀和数组那么对于下面的公式应该不难理解每次计算新位置的前缀和只要用前一个位置的和加上当前位置的元素即可那么对于第1个位置的前缀和就等于本身但是因为会出现f[0]如果不用vector创建数组的话要手动将f[0]置为0了解了公式之后代码的编写也变得简单了顺着思路创建两个数组对于每次查询只要知道左右位置的下标即可这里要注意因为区间包含左右端点所以实际是f[right]-f[left-1]代码部分注意前缀和可能int越界所以用long long类型防止出现越界#include iostream using namespace std; #includevector int main() { int n,m; cinnm; vectorint num(n1); vectorlong long f(n1); int left,right; f[0]0; for(int i1;in;i){ cinnum[i]; } for(int j1;jn;j){ f[j]f[j-1]num[j]; } for(int k1;km;k){ cinleftright; coutf[right]-f[left-1]\n; } return 0; }2.二维前缀和【模板】二维前缀和_牛客题霸_牛客网刚才是一维的前缀和这里进行了升维返回一块矩阵的元素和其实思路还是一样的创建两个矩阵一个原矩阵一个前缀和矩阵只不过这个前缀和我们需要分析一下怎么计算我画了一个三行四列的矩阵注意下标仍然是从1开始所以外层的蓝色矩阵和内层黑色矩阵之间的部分全部要是0才不会影响计算然后就是查询的操作例如某次查询输入2234注意这里我们要包含的矩阵部分是红色框部分对于22和34的位置是蓝色箭头的交汇点所以输入坐标之后取到的元素是坐标往左上角的第一个也就是图中的6和12那么就需要计算由6和12作为首尾的一个矩阵和结果应该是54讲解完坐标的细节就进入前缀和的计算例如某个元素处在D位置我们如果计算该位置的前缀和呢我们将矩阵从00到D位置进行分割出现了四块区域假设创建了一个原矩阵num和前缀和矩阵dp所以对于ABCD四块区域的和也就是ABCDdp[i][j]注意到BC区域的值不方便单独计算但是AB和AC可以公式也就是ABdp[i][j-1]ACdp[i-1][j]Adp[i-1][j-1]所以可以通过ABCD(AB)(AC)D-A的公式得出前缀和的公式dp[i][j]dp[i-1][j]dp[i][j-1]num[i][j]-dp[i-1][j-1]那么套用公式从11位置开始逐步计算所有位置的前缀和即可使用这样的方式得到前缀和矩阵之后就可以直接通过一次运算得到结果了这里也需要注意细节因为我们求的是两个红色元素之间的元素和也就是黄色部分加上这两个红色部分构成的矩阵但是光是前缀和相减会少减去B和C也就是绿色和粉色部分的元素所以采取合并的方式将AB和AC合并计算然后减去这两个部分因为多减去了一个A所以补上一个A注意要包含红色的元素所以A应该是x1-1和y1-1构成的矩阵有了刚才的铺垫这里就不再赘述怎么加减了代码部分#include iostream using namespace std; #includevector int main() { int n,m,q; int x1,x2,y1,y2; cinnmq; vectorvectorint num(n1,vectorint(m1)); vectorvectorlong long dp(n1,vectorlong long(m1)); for(int i1;in;i){ for(int j1;jm;j){ cinnum[i][j]; } } for(int i1;in;i){ for(int j1;jm;j){ dp[i][j]dp[i][j-1]dp[i-1][j]-dp[i-1][j-1]num[i][j]; } } for(int k1;kq;k){ cinx1y1x2y2; coutdp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]\n; } return 0; }3.寻找数组的中心下标724. 寻找数组的中心下标 - 力扣LeetCode这道题的目标很简单从左往右找到一个位置它的左侧元素和等于右侧元素和既然我们学会了前缀和那么后缀和自然也是同样的只不过计算顺序是从后往前所以我们创建两个数组一个前缀和数组一个后缀和数组注意这里比较时是不包含当前位置元素的所以前缀和对于第i个位置存储的是前i-1个元素的和后缀和也是不能包含当前元素那么就很简单了遍历一次数组每次对前缀和数组与后缀和数组的值进行比较判断即可代码部分class Solution { public: int pivotIndex(vectorint nums) { int lennums.size(); vectorint f(len);//前缀和 vectorint g(len);//后缀和 f[0]0; g[len-1]0; for(int i1;ilen;i){ f[i]f[i-1]nums[i-1]; } for(int jlen-2;j0;j--){ g[j]g[j1]nums[j1]; } for(int k0;klen;k){ if(f[k]g[k])return k; } return -1; } };4.除了自身以外数组的乘积238. 除了自身以外数组的乘积 - 力扣LeetCode这道题目和第三题几乎就是换了一种方式的前缀和以及后缀和只需要创建一个前缀积数组和一个后缀积数组即可注意不包含当前位置的元素代码部分注意f和g初始化时nums的下标要匹配对于元素因为前缀积第一个位置前面没有元素第二个位置要存放nums第一个元素本身所以将前缀积第一个位置初始化为1即可 后缀积最后一个位置同理class Solution { public: vectorint productExceptSelf(vectorint nums) { int lennums.size(); vectorint f(len); vectorint g(len); vectorint ans; f[0]1; g[len-1]1; for(int i1;ilen;i){ f[i]f[i-1]*nums[i-1]; } for(int jlen-2;j0;j--){ g[j]g[j1]*nums[j1]; } for(int k0;klen;k){ ans.push_back(f[k]*g[k]); } return ans; } };5.和为K的子数组560. 和为 K 的子数组 - 力扣LeetCode这道题同样可以使用前缀和的方法做只不过要加上哈希表的使用我们分析一下每遍历到一个位置只要子数组的结尾是当前位置是不是绝对不可能和前一个位置重复因为以前一个位置为结尾的子数组不包含当前位置所以我们要以当前位置作为子数组的结尾这样保证了子数组的不重复性对于目标值k也就是后半段区间的总和是k那么前半段总和就是sum-k所以我们把问题转换成每次遍历到一个新位置的时候查找前面的所有位置的前缀和是否存在sum-k有几组sum-k就存在几组子数组这里要注意一点每次遍历到新位置的时候当前位置的前缀和不能先入哈希表因为假如我现在查找到L位置的前缀和是sum-k那么[L1R]这个区间就是满足条件的一个子数组如果我先把当前位置的前缀和放入哈希表此时LR那么[R1R]是不存在这个区间的会出现逻辑错误那么如果我当前位置R这个位置的前缀和就等于k呢就会漏掉一种情况所以我们提前在哈希表中设置一个hash[0]1可以理解为在数组前面额外添加一个位置这个位置的前缀和是0然后就是哈希表的设置每次查找完一次前缀和将当前位置的前缀和放入哈希表代码部分class Solution { public: int subarraySum(vectorint nums, int k) { unordered_mapint, int hash; hash[0]1; int ret 0; int sum 0; for (auto e : nums) { sum e; if (hash.count(sum - k)) ret hash[sum - k]; hash[sum]; } return ret; } };6.和可被K惩处的子数组974. 和可被 K 整除的子数组 - 力扣LeetCode这里需要知道一个定理同余定理(a-b)%m0等价于a%mb%m简单证明一下(a-b)/mk那么a-bmk推出amkb两边同时对k取余a%kb%kmk%k因为mk%k0所以a%kb%k那么知道这个定理我们可以怎么解题呢如下图当前位置的前缀和是sum如果sum和前面某个前缀和p是同余的那么可以得出sum-p可以被k整除所以这里的哈希表我们每次存入前缀和对k取余的结果然后让sum也取余去查找这里还需要注意一点在C计算余数时如果前面的数字是负数余数也是负数但是不符合我们的要求我们的余数要是非负数例如-7%5-2而实际上应该是-2*53-7也就是余数为3所以我们要让余数加上k但是这样原本正确的余数就多了一个k只需要再%k即可去掉多余结果代码部分class Solution { public: int subarraysDivByK(vectorint nums, int k) { unordered_mapint, int hash; int sum 0; int ret 0; hash[0] 1; for (auto e : nums) { sum e; int r (sum % k k) % k; if (hash.count(r)) ret hash[r]; hash[r]; } return ret; } };7.连续数组525. 连续数组 - 力扣LeetCode这道题因为只有0和1我们可以将0进行数值的替换换成-1但是这并不影响结果因为只有元素A和B保证AB数量相等即可对AB的值没有要求不过AB不能相等这样替换有一个好处那就是计算前缀和的时候-1和1会进行抵消那么我们就可以根据这个特性得出如果某两个位置的前缀和相等那么它们中间是不是一定进行了等数量的1和-1就可以确定这个区间肯定是-1和1数量相等注意对于前缀和相等的L位置和R位置区间是[L1R]这一段那么逻辑就简单了每次得到前缀和就去前面找和它相等的前缀和取最大值即可不过还有一点要注意的是对于所有相等的前缀和我们应该取最左侧的哪个这样才是最长代码部分class Solution { public: int findMaxLength(vectorint nums) { for(auto e:nums){ if(e0)e-1; } int lennums.size(); unordered_mapint,int hash; //第一个int表示前缀和第二个表示下标 //记录每种前缀和的最左下标 hash[0]-1; int sum0; int maxn0; for(int i0;ilen;i){ sumnums[i]; if(!hash.count(sum))hash[sum]i; else maxni-hash[sum]maxn?i-hash[sum]:maxn;//三目运算 } return maxn; } };