//
// Created by 罗炳国 on 2023/8/2.
//

#ifndef PFJ_CODE15_PRODUCTEXCEPTSELF_H
#define PFJ_CODE15_PRODUCTEXCEPTSELF_H

#include "commonHeader.h"

/*
 *
 * 给你一个整数数组nums，返回 数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。
 * 题目数据 保证 数组nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
 * 请不要使用除法，且在O(n) 时间复杂度内完成此题。
 * 示例 1:
 * 输入: nums = [1,2,3,4]
 * 输出: [24,12,8,6]
 *
 * 2 <= nums.length <= 105
 * -30 <= nums[i] <= 30
 * 保证 数组nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/product-of-array-except-self
 * */

class code15_productExceptSelf {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int N = nums.size();
        vector<int> pre(N, 0);
        vector<int> tail(N, 0);
        vector<int> ans(N, 0);

        int preP = 1;
        int tailP = 1;
        for (int i = 0; i < N; i++) {
            preP *= nums[i];
            pre[i] = preP;
            tailP *= nums[N - 1 - i];
            tail[N - 1 - i] = tailP;
        }

        ans[0] = tail[1];
        ans[N - 1] = pre[N - 2];
        for (int i = 1; i < N - 1; i++) {
            ans[i] = pre[i - 1] * tail[i + 1];
        }
        return ans;
    }

};

#endif//PFJ_CODE15_PRODUCTEXCEPTSELF_H