XingHuiSamaの宝藏之地

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

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

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

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 105
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位 整数范围内

首先想到前缀乘和后缀惩

1. 算法核心思想

题目要求在不使用除法的情况下，计算除当前元素外其他所有元素的乘积。核心思路是：一个元素对应的最终结果，等于它左侧所有元素的乘积，乘以它右侧所有元素的乘积。为了实现这一点，代码通过空间换时间的策略，分别使用两个辅助数组 data1 和 data2，提前计算并记录下原数组每个位置对应的“前缀累乘结果”和“后缀累乘结果”。

2. 执行逻辑梳理

数组初始化： 创建两个长度与原数组 nums 相同的辅助数组 data1 和 data2，用于存放累乘数据。
计算前缀与后缀乘积： 通过一个 for 循环遍历原数组。
- 借助变量 s 从左向右累乘，将索引 0 到 i 的元素乘积存入 data1[i]。此时 data1[i] 代表包含当前元素在内的左侧连乘值。
- 同步借助变量 s2 从右向左累乘，将索引末尾到 nums.size() - i - 1 的元素乘积存入 data2[nums.size() - i - 1]。此时 data2 对应位置代表包含当前元素在内的右侧连乘值。
组合生成结果： 声明 result 数组，通过第二个 for 循环遍历，根据当前索引位置提取 data1 和 data2 的值进行组合计算：
- 当索引在首位（i == 0）：该元素左侧无数据，最终结果直接取其右侧所有元素的乘积，即 data2[1]。
- 当索引在末位（i == nums.size() - 1）：该元素右侧无数据，最终结果直接取其左侧所有元素的乘积，即 data1[i-1]。
- 当索引在中间： 最终结果等于其左侧的累乘值乘以右侧的累乘值，即 data1[i-1] * data2[i+1]。

class 除了自身以为数组的乘积 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> data1 = vector<int>(nums.size(), 0);
        vector<int> data2 = vector<int>(nums.size(), 0);

        int s = 1;
        int s2 = 1;
        for (int i = 0; i < nums.size(); i++) {
            s = s*nums[i];
            data1[i] = s;
            s2 = s2*nums[nums.size() - i - 1];
            data2[nums.size() - i - 1] = s2;
        }

        vector<int> result(nums.size(), 0);
        for (int i = 0;i < nums.size(); i++) {
            if (i == 0) {
                result[i] = data2[i+1];
            }
            else if (i == nums.size() - 1) {
                result[i] = data1[i-1];
            }
            else {
                result[i] = data1[i-1]*data2[i+1];
            }
        }

        return result;

    }
};

3. 复杂度分析

时间复杂度： O(n)。代码中包含两个同层级的 for 循环，分别完整遍历了数组一次，执行步数与数组长度呈线性关系。
空间复杂度： O(n)。算法在函数内部额外申请了两个长度为 n 的数组 data1 和 data2（输出数组 result 按题目规定不计入额外空间），因此内存开销随数组规模线性增长。