LeetCode刷题【剑指 Offer 66】构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

前年美团面试遇到过，哎，更新下（前缀 和×，积√），同力扣238题

当时没做出来，只是灵光一闪想到了可以全乘了然后除以各个数字，后来加了不能用除法的条件后，想了下觉得可能分段预先把个部分分段区间的乘积求起来，但是后来就没后来了。

最终结果可以直接在int[] a数组上修改，省一点空间？或者其实还可以再极限一点把int[] arr和int[] arr2声明成一个数组，然后在运算的key上做文章

class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        if (n==0){
            return a;
        }
        int[] arr = new int[n];
        int[] arr2 = new int[n];

        arr[0] = a[0];
        arr2[n-1] = a[n-1];
        for (int idx = 1; idx < n; idx++) {
            arr[idx] = a[idx]* arr[idx-1];
            int backIdx = n-idx-1;
            arr2[backIdx] = a[backIdx] * arr2[backIdx+1];
        }
        a[0] = arr2[1];
        a[n-1] = arr[n-2];
        for (int i = 1; i < a.length-1; i++) {
            a[i] = arr[i-1] * arr2[i+1];
        }
        return a;
    }
}

重新做这题，更新下单数组解法, 同力扣238题，不过238题的测试用例没有空数组的情况
思路还是一样的，就是先后更新的时候算的问题

class Solution {
    public int[] constructArr(int[] nums) {
        if (nums.length < 2){
            return nums;
        }
        int[] res = new int[nums.length];
        res[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i-1] * nums[i-1];
        }
        int preR =  nums[nums.length-1];
        for (int r = nums.length-2; r >= 0; r--) {
            res[r] *= preR;
            preR *= nums[r];
        }
        return res;
    }
}