题解 | #牛群重量积# 前缀和

知识点

前缀和

思路

不让用出发，那就预处理左边和右边的前缀和，找到每个位置对应的左右的长度之后乘一起得到答案。

时间复杂度

预处理的时间复杂度为

总体的时间复杂度为

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        vector<int> l(n + 1, 1);
        vector<int> r(n + 1, 1);
        for (int i = 1; i <= n; i ++) {
            l[i] = l[i - 1] * nums[i - 1];
        }
        for (int i = 1; i <= n; i ++) {
            r[i] = r[i - 1] * nums[n - i];
        }

        for (int i = 0; i < n; i ++) {
            int ans = l[max(0, i - 1)] * r[max(0, n - i - 2)];
            res.push_back(ans);
        }
        return res;
    }
};