Problem: 238. 除自身以外数组的乘积

题目描述

思路

思路1：

1.先求取数组的包括当前下标值得前后缀乘积（利用两个数组记录下来分别为leftProduct和rightProduct）
2.当求取一个下标为i的数组中的元素（除它之外元素的乘积时）即可得到为*leftProduct[i-1]rightProdugt[i+1];边界判断：i - 1 >= 0; i + 1 < n

思路2：不适用额外的空间

1.定义一个数组result，记录前缀积（该前缀积不包含当前下标的元素）
2.定义一个int类型变量rightProduct初始化为1，并从nums右边起，每次执行**result[i] = rightProduct;rightProduct = nums[i];

复杂度

思路1：
时间复杂度:

$O(n)$；其中$n$为数组nums的大小

空间复杂度:

$O(n)$

思路2：
时间复杂度:

$O(n)$；其中$n$为数组nums的大小

空间复杂度:

$O(1)$

Code

思路1：

class Solution {
public:/*** Prefix sum and Suffix sum* @param nums Given array* @return vector<int>*/vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> result(n);int leftProduct = 1;for (int i = 0; i < n; ++i) {result[i] = leftProduct;leftProduct *= nums[i];}int rightProduct = 1;for (int i = n - 1; i >= 0; --i) {result[i] *= rightProduct;rightProduct *= nums[i];}return result;}
};

思路2：

class Solution {
public:/*** Prefix sum and Suffix sum* @param nums Given array* @return vector<int>*/vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> result(n);int leftProduct = 1;for (int i = 0; i < n; ++i) {result[i] = leftProduct;leftProduct *= nums[i];}int rightProduct = 1;for (int i = n - 1; i >= 0; --i) {result[i] *= rightProduct;rightProduct *= nums[i];}return result;}
};