leetcode238：除自身以外数组的乘积

题目链接

leetcode

题目描述

一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
不使用 除法，且在 O(n) 时间复杂度内完成此题。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    左右乘积列表
    使用索引左侧所有数字的乘积和右侧所有数字的乘积（前缀与后缀）相乘得到答案。
    
    时间复杂度：O(n)
        其中 n 是数组的大小。
        预处理 left 和 right 数组、遍历计算结果，时间复杂度都是 O(n)。
    空间复杂度：O(n)
        left 和 right 数组的大小。
*/
class Solution_0 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0); // left 和 right 分别表示左右两侧的乘积列表
        vector<int> res(n);
        
        // left[i] 表示索引 i 左侧所有元素的乘积
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = nums[i-1] * left[i-1];
        }
        // right[i] 表示索引 i 右侧所有元素的乘积
        right[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            right[i] = nums[i+1] * right[i+1];
        }
        // 计算结果
        for (int i = 0; i < n; i++) {
            res[i] = left[i] * right[i];
        }

        return res;
    }
};

/*
    由于输出数组不算在空间复杂度内，所以将 L 或 R 使用输出数组来计算。
    把输出数组当作 L 数组来计算，再构造 R 数组得到结果。
    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);

        // res[i] 表示索引 i 左侧所有元素的乘积
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = nums[i-1] * res[i-1];
        }
        // R 表示右侧所有元素的乘积
        int R = 1;
        for (int i = n-1; i >= 0; i--) {
            res[i] = res[i] * R;
            R = R * nums[i];
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3,4},
        {-1,1,0,-3,3}
    };

    for (auto& num : nums_cases) {
        cout << "Input: ";
        printArray(num);

        vector<int> result = solution.productExceptSelf(num);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}