《算法闯关指南：优选算法--前缀和》--27.寻找数组的中心下标，28.除自身以外数组的乘积

LOTSO

发布于 2025-10-29 15:28:51

1600

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

🔥草莓熊Lotso：个人主页 ❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》 ✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

前言：

聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。

27. 寻找数组的中心下标

题目链接：

724. 寻找数组的中心下标 - 力扣（LeetCode）

题目描述：

题目示例：

解法（前缀和）：

算法思路：

从中心坐标的定义可知，除中心下标的元素外，该元素左边的【前缀和】等于该元素右边的【后缀和】。

因此，我们可以预处理出来两个数组，一个表示前缀和，另一个表示后缀和。
然后，我们可以用一个 for 循环枚举可能的中心下标，判断每一个位置的【前缀和】以及【后缀和】。如果二者相等，就返回当前下标。

C++算法代码：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n),g(n);
        //f[0]=0,g[n-1]=0;//可以不写，默认为0
        for(int i=1;i<n;i++)
            f[i]=f[i-1]+nums[i-1];
        for(int i=n-2;i>=0;i--)
            g[i]=g[i+1]+nums[i+1];
        
        for(int j=0;j<n;j++)
        {
            if(f[j]==g[j])
                return j;
        }
        return -1;
    }
};

算法总结&&笔记展示：

笔记字有点丑，大家见谅：

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

题目链接：

238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述：

题目示例：

解法（前缀和数组）：

算法思路：

注意题目的要求，不能使用除法，并且要在 O(N) 的时间复制度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。继续分析，根据题意，对于每一个位置的最终结果 ret[i] ，它是由两部分组成的：

nums[0] * nums[1] * nums[2] * …… * nums[i-1]
nums[i+1] * nums[i+2] * …… * nums[n-1]

于是，我们可以利用前缀和的思想，使用两个数组post和suf，分别处理出来两个信息：

post表示：i位置之前的所有元素，即【0，i-1】区间内所有元素的前缀乘积
suf表示：i位置之后的所有元素，即【i+1，n-1】区间内所有元素单独后缀乘积

然后再处理最终结果。

C++算法代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n),g(n),ret(n);
        f[0]=1,g[n-1]=1;
        for(int i=1;i<n;i++)
            f[i]=f[i-1]*nums[i-1];
        for(int j=n-2;j>=0;j--)
            g[j]=g[j+1]*nums[j+1];
        
        for(int i=0;i<n;i++)
        {
            ret[i]=f[i]*g[i];
        }
        return ret;
    }
};

算法总结&&笔记展示：

笔记字有点丑，大家见谅：

结语：

🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点：
👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长
❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量
⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用
💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑
🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解
技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！

结语：本文介绍了两个关于数组前缀和与后缀和的算法问题。第一个问题是寻找数组的中心下标，通过预处理前缀和与后缀和数组，找到左右和相等的中心位置。第二个问题是计算除自身以外数组的乘积，同样利用前缀积和后缀积数组，避免使用除法实现高效求解。两种方法都通过预处理数组优化时间复杂度至O(N)，适合处理类似问题。