网站添加关键字,营销型网站建设培训,网上国网推广,网站文章内容的选取目录 1.寻找数组的中心下标
2.除自身以外数组的乘积
3.和为k的子数组
4.可被k整除的子数组
5.连续数组 1.寻找数组的中心下标
. - 力扣#xff08;LeetCode#xff09;
class Solution {
public:int pivotIndex(vectorint nums) {int size nums.size();v…目录 1.寻找数组的中心下标
2.除自身以外数组的乘积
3.和为k的子数组
4.可被k整除的子数组
5.连续数组 1.寻找数组的中心下标
. - 力扣LeetCode
class Solution {
public:int pivotIndex(vectorint nums) {int size nums.size();vectorintf(size);vectorintg(size);f[0] nums[0];for(int i 1; i size; i){f[i] f[i-1]nums[i];}g[size-1] nums[size-1];for(int i size-2; i 0; i--){g[i] g[i1] nums[i];}for(int i 0; i size; i){if(f[i] g[i])return i;}return -1;}
}; 即中心下标左边与右边的元素和相等如果没有某一侧没有元素那么值为0. 因为是加法运算那么左右元素相等的情况加上中心元素左右元素依然相等。 f[i]为前缀和表示从0到i位置的数组元素和递推公式为 f[i] f[i-1]nums[i]; g[i]为后缀和表示从 size-1 到i位置的数组元素和递推公式为·g[i] g[i1] nums[i]; 初始化时f【0】g【size-1】为0不干扰运算
2.除自身以外数组的乘积
. - 力扣LeetCode
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int size nums.size();vectorintf(size);vectorintg(size);vectorintret(size);f[0] 1;g[size-1] 1;for(int i 1; i size; i){f[i] f[i-1]*nums[i-1];}for(int i size-2; i 0; i--){g[i] g[i1]*nums[i1];}for(int i 0; i size; i){ret[i] f[i]*g[i];}return ret;}
}; 即某下标左边与右边的元素的积如果没有某一侧没有元素那么值为1. f[i]为前缀积表示从0到i-1位置的数组元素积递推公式为 f[i] f[i-1]*nums[i-1]; g[i]为后缀积表示从 size-1 到i1位置的数组元素和递推公式为·g[i] g[i1] * nums[i1]; 初始化时f【0】g【size-1】为1不干扰运算
3.和为k的子数组
. - 力扣LeetCode
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,inthash;int sum 0;int ret 0;hash[0] 1;for(auto ch: nums){sum ch; ret hash[sum-k];hash[sum];}return ret;}
}; 因为数组中的元素有正有负并不具有单调性因此不能使用滑动窗口那么我们使用前缀和。 以下标为i的位置为终点dp【i】为从nums【0】加到nums【i】的和 1 6 -3 2 9 .....x 0 1 2 3 4.... i 要想找到其中一段子数组和为k可以等效为找从0向后找一个子数组和为dp【i】-k。 因为每次只找i之前的位置因此我们不需要真的创建一个前缀和只需要记录一个变量sum来记录此时的前缀和。 创建一个哈希表intint分别存储某个前缀和的值和它的数目。 前缀和sum从0开始加入哈希表因此会缺失数组中无元素的情况所以我们应该初始化hash【0】 1. 我们每遍历到一个前缀和sum的时候只需要加上已经在hash中存储的即i位置之前的前缀和中是否有值为sum-k加上即可然后再加上本次增添的前缀和
4.可被k整除的子数组
. - 力扣LeetCode
class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,inthash;int sum 0;int ret 0;hash[0] 1;for(auto ch: nums){sum ch; ret hash[((sum%k)k)%k];hash[((sum%k)k)%k];}return ret;}
};
思路同3完全相同
注意点1.c和java中负数取余操作为负数,因此我们需要把取余操作的值取余的值再取余。
2.我们哈希表中存的是前缀和取余后的值。原因如下
0 1 2 3 4 ....i
假设从下标4到i的数组和能被k整除即前缀和i-前缀和3% k 0
根据同余定理前缀和i % k 前缀和3 % k。
5.连续数组
. - 力扣LeetCode
class Solution {
public:int findMaxLength(vectorint nums) {for(auto ch : nums){if(ch 0)ch -1;}int size nums.size();unordered_mapint,inthash;int sum 0;hash[0] 1;int ret 0;for(int i 0; i size; i){sum nums[i];if(hash[sum])ret max(ret,i2-hash[sum]);else hash[sum] i2;}return ret;}
}; 直接做不好做我们先把0转化为-1这样子当0与1数目相等时其和为0。 这样我们就把题目转化为类似第三题的和为k的数组此时和为0. 因此我们只需要寻找两个前缀和相等的数组将他们的下标相减即可。 所以我们哈希表中储存该下标hash[0]中储存-1. 接着我们遍历数组每次求出前缀和的时候到哈希表中查看如果已经储存下标那么我们相减。并与前面已经求出的下标差求最大否则我们把下标填入。下标只需要更新最前面一个因为向后更新时距离永远是更小的。 但是在判断条件的时候我们遇到了问题若更新出的数组下标为0那么我们将无法判断因此我们统一将数组下标2这样结果不变。
