Dx's Tech Notes

4.除自身以外数组的乘积

2 min read

  • 2.10

    • 想起了左边的处理，没想到右边的处理（从 n-1 开始，使用一个 right 变量来存储i-1 的数值）

  • 1.24

    • 算一下每个数左边的乘积，在乘上右边的乘积 假设有 4 个人排成一排，每个人手里举着一个数字：[A, B, C, D]。 现在，每个人都要算出除了自己以外，其他所有人的数字乘积。

    以 C（第 3 个人）为例，他需要的答案是：$A \times B \times D$。 我们可以把这个答案切成两半来看：

    • 左半边：C 左边所有人的乘积，也就是 $A \times B$。
    • 右半边：C 右边所有人的乘积，也就是 $D$。

    所以，C 的最终答案 = (左半边) $\times$ (右半边)。

    • “左边先乘完存着，右边边乘边补上。”
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        answer[0] = 1;
        for(int i=1;i<n;i++){
            answer[i] = answer[i-1]*nums[i-1];
        }
// 2️⃣ 从右往左计算右边的乘积，并累乘到结果中
        int right =1;
        for(int i = n-1;i>=0;i--){
            answer[i] = answer[i]*right;
            //这里的right就==上面的answer,累计乘的结果
            right = right*nums[i];
        }
        return answer;
    }
}

Graph View