描述

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例

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

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

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

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解题思路

  • 如果没有限制时间复杂度为 O(n),空间复杂度限制为 O(1) (不计输出数组)，这道题的解法应该有很多，所以我想先从这个限制条件入手，看怎么样才能满足条件。
  • 用前缀和是肯定的，关键是，当记录到 i 时，i 前的元素的乘积是可以知道的，满足 O(n) O(1) ，但是 i 之后的元素的乘积如果通过前缀和计算呢？
  • 考虑先从前往后一次遍历，确定每个位置之前的元素乘积之和，然后再从后往前遍历，对于每个位置 i ，再乘以当前的乘积之和，即 n - 1 到 i + 1 的乘积之和，这样就完整了。我们通过复用了输出数组，保证空间复杂度还是为 O(1).

代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int tmpSum = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= tmpSum;
            tmpSum *= nums[i];
        }
        return res;
    }
}