寻找数组中心下标与除自身以外数组的乘积 - 前缀和技巧

除自身以外数组的乘积

解法（前缀和数组）

算法思路

注意题目的要求，不能使用除法，并且要在 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;
    }
};

算法总结&&笔记展示