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

题目

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

解法

这个问题要求我们计算一个数组 answer，其中每个元素 answer[i] 是数组 nums 中除 nums[i] 以外的所有元素的乘积，且不能使用除法，并要求时间复杂度为 O(n)。我们可以使用前缀积和后缀积的技巧来高效地解决问题。

思路：

前缀积：对于每个位置 i，计算它左边所有元素的乘积。
后缀积：对于每个位置 i，计算它右边所有元素的乘积。
最终结果：对于每个位置 i，结果 answer[i] 就等于它左边的前缀积乘以右边的后缀积。

通过这种方式，我们可以避免直接使用除法。

步骤：

创建一个 answer 数组，首先存储每个位置的前缀积。
再遍历数组，从右向左计算后缀积，并同时更新 answer 数组中的结果。

代码实现：

#include <iostream>
#include <vector>std::vector<int> productExceptSelf(const std::vector<int>& nums) {int n = nums.size();std::vector<int> answer(n, 1);  // 初始化结果数组，所有元素设为 1// 计算前缀积for (int i = 1; i < n; ++i) {answer[i] = answer[i - 1] * nums[i - 1];  // 当前元素存放左边所有元素的乘积}// 计算后缀积并同时更新结果数组int suffix = 1;  // 记录后缀积for (int i = n - 1; i >= 0; --i) {answer[i] = answer[i] * suffix;  // 将前缀积乘以后缀积suffix *= nums[i];  // 更新后缀积}return answer;
}int main() {std::vector<int> nums = {1, 2, 3, 4};std::vector<int> result = productExceptSelf(nums);// 输出结果for (int num : result) {std::cout << num << " ";}return 0;
}

解释：

前缀积部分：
- 从左到右遍历数组，answer[i] 存储的是 nums 数组中第 i 个元素左侧所有元素的乘积。
- 例如对于 nums = {1, 2, 3, 4}，计算完前缀积后的 answer 数组是 {1, 1, 2, 6}。
后缀积部分：
- 从右到左遍历数组，同时维护一个变量 suffix，它表示当前元素右侧所有元素的乘积。
- 在每一步中，answer[i] 会乘以 suffix，并更新 suffix 为当前元素的乘积。

示例：

假设 nums = {1, 2, 3, 4}，执行过程如下：

前缀积计算后：
- answer = {1, 1, 2, 6}
后缀积计算后：
- 计算从右往左：
  - suffix = 1，初始值，乘以 answer[3] = 6，更新 suffix = 4。
  - suffix = 4，乘以 answer[2] = 2，更新 suffix = 12。
  - suffix = 12，乘以 answer[1] = 1，更新 suffix = 24。
  - suffix = 24，乘以 answer[0] = 1。