算法实战：前缀和与后缀和解决中心下标及数组乘积问题

寻找数组的中心下标

题目描述： 给定一个整数数组 nums，请找到一个索引位置，使得该位置左侧元素之和等于右侧元素之和。如果存在多个这样的位置，返回最小的那个；如果不存在，返回 -1。

示例： 输入：nums = [1, 7, 3, 6, 5, 6] 输出：3 解释：索引 3 左侧和为 1 + 7 + 3 = 11，右侧和为 5 + 6 = 11。

解法思路

要找到这个'平衡点'，核心在于快速计算每个位置左右的和。如果每次遍历都重新求和，时间复杂度会达到 O(N^2)。利用前缀和的思想，我们可以预先计算出每个位置的左侧累积和与右侧累积和，从而将查询降为 O(1)。

具体做法是构建两个辅助数组：

1. leftSum[i] 表示 i 左侧所有元素的和。
2. rightSum[i] 表示 i 右侧所有元素的和。

遍历数组时，只要发现 leftSum[i] == rightSum[i]，当前的 i 就是我们要找的中心下标。

C++ 代码实现

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        // f 存储左侧前缀和，g 存储右侧后缀和
        vector<int> f(n, 0), g(n, 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;
    }
};

---

除自身以外数组的乘积

题目描述： 给你一个整数数组 nums，请你返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。注意：不能使用除法，且要求时间复杂度为 O(N)。

示例： 输入：nums = [1, 2, 3, 4] 输出：[24, 12, 8, 6] 解释：answer[0] = 2 * 3 * 4 = 24，以此类推。

解法思路

这道题的限制条件比较苛刻，不能用除法，意味着我们不能先算出总乘积再除以当前元素。我们需要分别计算每个位置左侧的乘积和右侧的乘积。

类似于前缀和的思路，我们可以维护两个数组：

1. prefixProd[i] 表示 i 左侧所有元素的乘积（即 nums[0] * ... * nums[i-1]）。
2. suffixProd[i] 表示 i 右侧所有元素的乘积（即 nums[i+1] * ... * nums[n-1]）。

最终结果 answer[i] 即为这两部分的乘积。这样既满足了 O(N) 的时间要求，也避免了除法操作。

C++ 代码实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1), suffix(n, 1), result(n);
        
        // 计算左侧前缀乘积
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        
        // 计算右侧后缀乘积
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }
        
        // 组合结果
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }
        
        return result;
    }
};