当前位置: 首页> 文旅> 旅游 > 前缀和(更新中)

前缀和(更新中)

时间:2025/7/11 7:40:58来源:https://blog.csdn.net/myhhhhhhhh/article/details/140794293 浏览次数:0次

目录

1.寻找数组的中心下标

2.除自身以外数组的乘积

3.和为k的子数组

4.可被k整除的子数组

5.连续数组


1.寻找数组的中心下标

. - 力扣(LeetCode)

class Solution {
public:int pivotIndex(vector<int>& nums) {int size = nums.size();vector<int>f(size);vector<int>g(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[i+1] + 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[i+1] + nums[i];

        初始化时,f【0】,g【size-1】为0,不干扰运算

2.除自身以外数组的乘积

. - 力扣(LeetCode)

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int size = nums.size();vector<int>f(size);vector<int>g(size);vector<int>ret(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[i+1]*nums[i+1];}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 到i+1位置的数组元素和,递推公式为·g[i] = g[i+1] * nums[i+1];

        初始化时,f【0】,g【size-1】为1,不干扰运算

3.和为k的子数组

. - 力扣(LeetCode)

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int>hash;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,来记录此时的前缀和。

        创建一个哈希表<int,int>分别存储某个前缀和的值,和它的数目。

        前缀和sum从0开始,加入哈希表,因此会缺失数组中无元素的情况,所以我们应该初始化hash【0】 = 1.

        我们每遍历到一个前缀和sum的时候,只需要加上已经在hash中存储的,即i位置之前的前缀和中,是否有值为sum-k,加上即可,然后再加上本次增添的前缀和

4.可被k整除的子数组

. - 力扣(LeetCode)

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int>hash;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(vector<int>& nums) {for(auto& ch : nums){if(ch == 0)ch = -1;}int size = nums.size();unordered_map<int,int>hash;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,i+2-hash[sum]);else hash[sum] = i+2;}return ret;}
};

        直接做不好做,我们先把0转化为-1,这样子当0与1数目相等时,其和为0。

        这样我们就把题目转化为类似第三题的和为k的数组,此时和为0.

        因此我们只需要寻找两个前缀和相等的数组,将他们的下标相减即可。

        所以我们哈希表中储存该下标,hash[0]中储存-1.

        接着我们遍历数组每次求出前缀和的时候,到哈希表中查看,如果已经储存下标,那么我们相减。并与前面已经求出的下标差求最大,否则我们把下标填入。下标只需要更新最前面一个,因为向后更新时距离永远是更小的。

        但是在判断条件的时候我们遇到了问题,若更新出的数组下标为0,那么我们将无法判断,因此我们统一将数组下标+2,这样结果不变。

关键字:前缀和(更新中)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: