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

时间复杂度：O(n)，空间复杂度：O(1)。

028 除自身以外数组的乘积

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

算法思路

对于任意位置 i，结果由两部分组成：i 左侧所有数的乘积 乘以 i 右侧所有数的乘积。 为了节省空间，我们可以复用输出数组来存储左侧乘积，再引入一个变量动态维护右侧乘积，从而在遍历过程中完成计算。这样辅助空间复杂度仅为 O(1)。

算法实现

C++ 实现

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        
        // 计算左侧乘积并存入 result
        result[0] = 1;
        for (int i = 1; i < n; ++i) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // 从右向左遍历，用变量维护右侧乘积并累乘到 result
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; --i) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return result;
    }
};

时间复杂度：O(n)，空间复杂度：O(1) 额外空间。

Java 实现

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        // 计算左侧乘积并存入 result
        result[0] = 1;
        for (int i = 1; i < n; ++i) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // 从右向左遍历，用变量维护右侧乘积并累乘到 result
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; --i) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return result;
    }
}

时间复杂度：O(n)，空间复杂度：O(1) 额外空间。

这两道题是前缀和与后缀思想的典型应用。掌握这种'左右拆分'的思路，能帮你快速应对类似的累积计算问题。面试中遇到此类题目，优先考虑能否通过预处理或复用空间来优化复杂度。