题解54 | 乘积如风，常伴吾身#除自身以外数组的乘积#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector
     */
    vector<int> timesExceptSelf(vector<int>& nums) {
        // write code here
        int n = nums.size();
        vector<int> left(n,0),right(n,0);

        left[0] = 1;
        right[n-1] = 1;

        for (int i = 1; i < n; i++) {
            left[i] = nums[i-1]*left[i-1];
            right[n-1-i] = nums[n-i]*right[n-i];
        }
        
        for (int i = 0; i < n; i++) {
            left[i] *= right[i];
        }
        

        return left;
    }
};

算法基本思想：

给定一个整数数组nums，要求返回一个新的数组，其中每个元素是除了自身以外所有元素的乘积。

可以通过左右两个数组分别记录每个元素左边所有元素的乘积和右边所有元素的乘积（有0也不怕，反正不用除法），然后将两个数组对应位置的元素相乘即可得到结果。

时间复杂度：O(n)，其中n是数组的长度。

空间复杂度：O(n)，需要使用两个额外的数组来记录左右乘积。