网站建立数据库,李洋网站建设,企信网查不到公司怎么办,万能搜索目录 热身#xff1a;
寻找数组的中心下标
题解#xff1a;
代码#xff1a;
进阶#xff1a;
除自身之外数组的乘积
题解#xff1a;
代码#xff1a;
和为K的子数组
题解#xff1a;
代码#xff1a;
和可被 K 整除的子数组
题解#xff1a;
同余定理…目录 热身
寻找数组的中心下标
题解
代码
进阶
除自身之外数组的乘积
题解
代码
和为K的子数组
题解
代码
和可被 K 整除的子数组
题解
同余定理
为什么需要修正负数取模
代码
连续数组
代码 热身
寻找数组的中心下标
724. 寻找数组的中心下标 - 力扣LeetCodehttps://leetcode.cn/problems/find-pivot-index/description/ 题解
运用前缀和就可以解决这个问题注意在本题中中心下标的左侧数之和、右侧数之和均不包括中心下标的数。
我们定义前缀和、后缀和数组根据题目要求对前缀和数组的最左端、后缀和数组的最右端初始化为0。
代码
class Solution {
public:int pivotIndex(vectorint nums) {int nnums.size();vectorint f(n);//前缀和vectorint g(n);//后缀和f[0]g[n-1]0;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;}
};
进阶
除自身之外数组的乘积
238. 除自身以外数组的乘积 - 力扣LeetCodehttps://leetcode.cn/problems/product-of-array-except-self/description/ 题解
由于题目要求不用除法所以我们不可以算出数组全部元素的乘积后再去除以 nums[ i ] 来得到答案。 在寻找数组的中心下标中我们算出了 nums[ i ] 左侧和、右侧和我们可以按照这个思路算出 nums[ i ] 左侧乘积、右侧乘积把左右两侧乘积相乘就可以得到除自身之外数组的乘积。 代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int nnums.size();vectorint f(n);//左侧乘积vectorint g(n);//右侧乘积vectorint ret(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];for(int i0;in;i){ret[i]f[i]*g[i];}return ret;}
};
和为K的子数组
560. 和为 K 的子数组 - 力扣LeetCodehttps://leetcode.cn/problems/subarray-sum-equals-k/description/ 题解 如下图假设 k 10在给定的数组中发现下标 2 ~ 5 的数组和 k而这一部分数组和恰好为下标 0 ~ 5 的前缀和 - 下标 0 ~ 1 的前缀和假设前缀和数组为 sum则 K sum[ 5 ] - sum[ 1 ] 所以我们可以用前缀和数组快速得到和为 K 的子数组。 为了获得和为 K 的子数组的个数我们可以在计算前缀和的同时用哈希表记录每一个前缀和出现的次数。 比如 K sum[ 5 ] - sum[ 1 ] 可以交换位置变为 sum[ 5 ] - K sum[ 1 ]由于记录了 sum[ 1 ] 出现的次数为 1 次这样就可以得出当前和为 K 的子数组的个数为 1 个。 由于我们用哈希表记录了每一个前缀和出现的个数所以前缀和的计算可以不采用数组。
可能会出现以下情况前缀和 sum - k 0但是哈希表中记录的前缀和并不存在 0怎么处理 既然哈希表中不存在前缀和 0那我们可以先放一个 0 进去并把出现的次数设置为 1.
代码
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;int ret0,sum0;hash[0]1;for(int i0;inums.size();i){sumnums[i];if(hash.count(sum-k)) {rethash[sum-k];}hash[sum];}return ret;}
};
和可被 K 整除的子数组
974. 和可被 K 整除的子数组 - 力扣LeetCodehttps://leetcode.cn/problems/subarray-sums-divisible-by-k/description/ 题解
同余定理
假设 a % k b % k 则 a - b ) % k 0.
举个例子假设 k 523 % 5 13 % 5则23 - 23 % 5 0.
我们可以运用同余定理来解决这道题 和上一题的思路相似我们用 i 遍历数组计算出下标 0 ~ i 的前缀和 sum用哈希表记录 sum % K 出现的次数如果 sum % K 曾经出现过则存在和可被 K 整除的子数组返回值 次数。 以示例 1 为例假设返回值为 ret比如下标 0 ~ 1 的前缀和取模后为 4而下标 0 的前缀和取模后也为 4 而在此之前取模后为 4 出现的次数为 1根据同余定理子数组 [ 5 ] 可以被 K 整除ret 1同理下标 0 ~ 2 的前缀和取模后为 4而在此之前取模后为 4 出现的次数为 2 所以此时 ret2 分别为 [ 5 ] , [ 5 , 0 ] , [ 0 ] 下标 0 ~ 4 的前缀和取模后为 4而在此之前取模后为 4 出现的次数为 3所以此时 ret 3 和可被 K 整除的子数组有 6 个分别为 [ 5 ] , [ 5 , 0 ] , [ 0 ], [ 0, -2 , -3 ] , [ -2 , -3 ] [ 5 , 0, -2 , -3 ] 以此类推。 注意 0 也可以被 K 整除 为什么需要修正负数取模
我们观察下面的例子 存在子数组 [ 2, 3, 4 ] 的和可以被 3 整除但是这在前缀和中无法体现出来。
再举个例子
1、 7 % 3 1 , ( -2 ) % 3 -2 但 [ 7 - ( -2 ) ] % 3 0
2、 - 2 % 3 -2 , ( -5 ) % 3 -2 [ -2 - ( -5 ) ] % 3 0 。 可以看出当 a、b 同正同负时 a % k b % k 可以推出 a - b ) % k 0可以推出和可被 K 整除的子数组但 a、b一正一负时就没办法推出。 为了让同余定理在一正一负的情况下也可以成立我们可以对负数取模进行修正把取模后的结果修改为正数这样 a、b 就都是正数 int r(sum%kk)%k; 再回到一开始举的例子通过修正取模后就可以得到正确的结果 代码
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {int sum0,ret0;unordered_mapint,int hash;hash[0]1;for(int i0;inums.size();i){sumnums[i];int r(sum%kk)%k;if(hash.count(r)) rethash[r];hash[r];}return ret;}
};
连续数组
525. 连续数组 - 力扣LeetCode 这道题用到的方法比较巧妙利用了前缀和
1、如果 nums[ i ] 为 0则 sum -1
2、如果 nums[ i ] 为 1则 sum 1。 如果此时的前缀和 sum 在之前已经出现过了假设上一次出现的下标为 j说明 i 和 j 中间的这段数组的 0 和 1 的数量相等只有相等了才会相互抵消前缀和才会再次变为 sum。 代码
class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;hash[0]-1;int ret0;int sum0;for(int i0;inums.size();i){sum(nums[i]0?-1:1);if(hash.count(sum)) retmax(ret,i-hash[sum]);else hash[sum]i;}return ret;}
};
