前缀和篇——繁星斗斗数字交织中，觅得效率明月辉光（2）

用户11379153

发布于 2025-11-05 15:48:26

890

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

前言

上篇我们介绍了前缀和在一维情况和二维情况下的两大基本模板，本篇将结合具体题目分析讲解，深化我们对于前缀和算法的理解运用。

一. 寻找数组的中心下标

1.1 题目链接：https://leetcode.cn/problems/find-pivot-index/

1.2 题目分析：

在此之前，我们先来理解什么是中心下标：即左侧所有元素相加之和等于右侧所有元素相加之和。题目具体要求如下：

如果存在多个中心下标，返回最靠近左侧的那个
如果不存在，则返回-1
下标为0的左侧和为0，下标为n-1的右侧和为0

1.3 思路讲解：

暴力解法（会超时）：

采取直接遍历法，每次遍历一个元素时，计算其左侧之和与右侧之和是否相等，相等则直接返回该元素下标。
若循环结束仍未返回，则说明不存在，返回-1 此法的大量冗余计算是一定会超时的，而计算和的简化方法可以考虑使用前缀和。 前缀和： 该题的核心判断即为左侧和是否等于右侧和，我们可以用两个数组分别记录前缀和与后缀和，即可简化时间消耗。
前缀和数组：sums1[i]表示i的左侧所有元素累加之和
后缀和数组：sums2[i]表示i的右侧所有元素累加之和

1.4 代码实现：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        vector<int> sums1(n);//前缀和数组
        vector<int> sums2(n);//后缀和数组
        //处理前缀和数组
        for(int i=1;i<nums.size();i++)
        {
            sums1[i]=sums1[i-1]+nums[i-1];

        }
        //处理后缀和数组
        for(int i=nums.size()-2;i>=0;i--)
        {
            sums2[i]=sums2[i+1]+nums[i+1];
        }
        //匹配比较
        for(int i=0;i<n;i++)
        {
            if(sums1[i]==sums2[i])
            {
                return i;
            }
           

        }
        return -1;
        
    }
};

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

2.1 题目链接：https://leetcode.cn/problems/product-of-array-except-self/

2.2 题目分析：

题目要求返回一个与原数组同规模的数组
数组内每个元素的值为原数组内除去该元素外，所有其余元素的乘积
不允许使用除法

2.3 思路讲解：

暴力解法： 创建一个数组，之后直接遍历，每一个元素都在原数组的基础上累乘求解，在数据量较大时一定会超时。

前缀和：

该题思路与上题类似，由于不能使用除法，我们可以通过记录前缀乘积与后缀乘积，之后二者相乘即为所求元素。
该题中注意dp1[0]和dp2[n-1]都要初始化为1，因为此时为乘积，而非加和。

2.4 代码实现：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp1(n);//前缀乘积数组
        vector<int> dp2(n);//后缀乘积数组
        vector<int> ret(n);//返回数组
        dp1[0]=dp2[n-1]=1;//注意初始化为1
        //处理前缀数组
        for(int i=1;i<n;i++)
        {
            dp1[i]=dp1[i-1]*nums[i-1];
        }
        //处理后缀数组
        for(int i=n-2;i>=0;i--)
        {
            dp2[i]=dp2[i+1]*nums[i+1];
        }
        //插入返回值
        for(int i=0;i<n;i++)
        {
            int temp=dp1[i]*dp2[i];
            ret[i]=temp;
        }
        return ret;
    }
};

三. 和为k的子数组

3.1 题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/

3.2 题目分析：

题目要求统计并返回数组中和为k的子数组的个数。

3.3 思路讲解：

设i为数组中的任意位置，sums[i]表示[0,i]的数组元素和。则数组中和为k的子数组，即代表[x,i]内的和为k，[0,x]内的和为sums[i]-k。因此，问题就转化为有多少个[0,x]的前缀和为sums[i]-k.具体步骤如下：

我们可以使用哈希表来存储前缀和的值和该值出现的次数
则和为k的子数组的个数就等于hash[sums[i]-k]

3.4 代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;//记录前缀和及其出现的次数
        int sum=0,ret=0;
        hash[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            if(hash.count(sum-k))//存在
            {
                ret+=hash[sum-k];
            }//更新个数
            hash[sum]++;//更新哈希表
        }
        return ret;
        
    }
};