算法实战：寻找数组中心下标与除自身外数组乘积（前缀和技巧）

算法实战：前缀和进阶

在数组处理问题中，前缀和（Prefix Sum）是一种将区间查询优化到 O(1) 的经典技巧。今天我们来深入两个典型场景：寻找数组的中心下标，以及计算除自身以外数组的乘积。这两个问题看似不同，核心都在于利用预处理降低时间复杂度。

27. 寻找数组的中心下标

题目描述： 给定一个整数数组 nums，找到并返回该数组的中心下标。如果不存在，则返回 -1。 中心下标是指左侧所有元素之和等于右侧所有元素之和的下标。

解题思路： 直观的想法是遍历每个位置，分别计算左边和右边的和。但这样会导致 O(N^2) 的复杂度。我们可以利用前缀和的思想进行优化：

1. 预处理：构建两个辅助数组。f[i] 存储 nums[0] 到 nums[i-1] 的和（即 i 左侧的和），g[i] 存储 nums[i+1] 到 nums[n-1] 的和（即 i 右侧的和）。
2. 枚举判断：遍历数组，当 f[i] == g[i] 时，当前下标即为所求。
3. 边界处理：注意首尾元素的左右和默认为 0。

代码实现：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return -1;
        
        // f[i] 表示 i 左侧所有元素的和
        vector<int> f(n, 0);
        // g[i] 表示 i 右侧所有元素的和
        vector<int> 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;
    }
};

工程师提示：实际面试中，为了节省空间，我们通常只需要维护一个总和变量，遍历时动态计算左侧和即可，无需额外开辟两个数组。这里展示双数组是为了更直观地对应'前缀'与'后缀'的概念。

---

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

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

解题思路： 既然不能用除法，那就不能先算总乘积再除以当前值。我们需要把结果拆分为两部分：

1. 当前位置左侧所有元素的乘积（前缀积）。
2. 当前位置右侧所有元素的乘积（后缀积）。

最终结果 answer[i] = left_product[i] * right_product[i]。

具体步骤如下：

1. 初始化 f 数组记录左侧乘积，g 数组记录右侧乘积。
2. 正向遍历填充 f，反向遍历填充 g。
3. 合并结果。

代码实现：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1); // 左侧乘积，初始化为 1
        vector<int> g(n, 1); // 右侧乘积，初始化为 1
        vector<int> ret(n);
        
        // 计算左侧前缀积
        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;
    }
};

总结： 这两个问题都展示了前缀和（或前缀积）的核心价值：通过一次线性扫描预处理数据，将后续的查询操作从 O(N) 降为 O(1)。在处理涉及区间统计、累积运算的题目时，优先考虑这种空间换时间的策略，往往能避开暴力解法的性能瓶颈。