class Solution {
    // 题目要求o(n)的时间复杂度
    // 题目类型dp
    public int[] productExceptSelf(int[] nums) {
        //除nums[i]之外的所有数的乘积也就是将nums[i]当做1
        // 可以计算这个数左乘积和右乘积
        // 用三个数组分别存储前缀、后缀和乘积
        // 对于元素nums[0]，我们设定初始值left[0] = 1;
        // 对于元素nums[nums.length - 1] 设定初始值right[nums.length - 1] = 1;
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] res = new int[n];
        left[0] = 1;right[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        for (int j = n - 2; j >= 0; j--) {
            right[j] = right[j + 1] * nums[j + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }
}