算法必刷 100 题：寻找数组中心下标与除自身外乘积

Java 实现

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        if (n == 0) return -1;
        
        // lsum[i] 表示 [0, i-1] 区间和
        int[] lsum = new int[n];
        // rsum[i] 表示 [i+1, n-1] 区间和
        int[] rsum = new int[n];
        
        // 填充左侧和
        for (int i = 1; i < n; i++) {
            lsum[i] = lsum[i - 1] + nums[i - 1];
        }
        
        // 填充右侧和
        for (int i = n - 2; i >= 0; i--) {
            rsum[i] = rsum[i + 1] + nums[i + 1];
        }
        
        // 比较
        for (int i = 0; i < n; i++) {
            if (lsum[i] == rsum[i]) {
                return i;
            }
        }
        
        return -1;
    }
}

注意： 上述实现使用了额外的数组存储前缀和后缀信息，因此空间复杂度为 O(n)，而非 O(1)。若追求极致空间优化，可结合总和计算将空间降至 O(1)，但会增加一次遍历或逻辑复杂度。

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

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

算法思路

对于任意位置 i，结果由两部分组成：

1. 左侧所有元素的乘积：nums[0] * ... * nums[i-1]
2. 右侧所有元素的乘积：nums[i+1] * ... * nums[n-1]

这同样是前缀思想的变体——前缀积与后缀积。我们不需要真的求出整个数组的总乘积再除以当前值（因为涉及除法和零的处理），而是直接分别计算左右两侧的累积乘积。

代码实现

C++ 实现

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

Java 实现

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] lprod = new int[n];
        int[] rprod = new int[n];
        
        // 初始化边界
        lprod[0] = 1;
        rprod[n - 1] = 1;
        
        // 计算左侧前缀积
        for (int i = 1; i < n; i++) {
            lprod[i] = lprod[i - 1] * nums[i - 1];
        }
        
        // 计算右侧后缀积
        for (int i = n - 2; i >= 0; i--) {
            rprod[i] = rprod[i + 1] * nums[i + 1];
        }
        
        // 生成结果
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = lprod[i] * rprod[i];
        }
        
        return ret;
    }
}

总结

这两道题的核心都在于避免重复计算。通过预处理将左右两侧的信息存储在数组中，我们在主循环中只需 O(1) 的时间就能得到当前位置的结果。虽然牺牲了 O(n) 的空间，但在大多数面试场景下，这种以空间换时间的策略是非常高效且易于理解的。实际工程中，如果内存受限，可以进一步优化为单次遍历或两次遍历配合变量累加的方式。