Hot100 - 除自身以外数组的乘积

Hot100 - 除自身以外数组的乘积

最佳思路：

此问题的关键在于通过两次遍历，分别计算从左侧和右侧开始的累积乘积，以此避免使用额外的除法操作。

时间复杂度：

该算法的时间复杂度为 O(n)，因为我们只需要遍历数组两次。

思路解析：

1. 初始化两个辅助数组 lefti 和 righti，分别用来存储从左到右和从右到左的累积乘积。
2. 第一次遍历：从左到右计算每个位置的左侧累积乘积，存储在 lefti 中。
3. 第二次遍历：从右到左计算每个位置的右侧累积乘积，存储在 righti 中。
4. 结果计算：利用 lefti 和 righti 数组，逐一计算除自身以外的乘积。最终，直接用 lefti[i-1] 和 righti[i+1] 来获得该位置的结果。

算法优化：

使用两个额外的数组来存储左右乘积信息，而不是直接修改原数组。这样可以避免在计算时出现覆盖问题。

代码实现：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 初始化累积乘积变量
        int left = 1;
        int right = 1;
        
        // 创建左右乘积的辅助数组
        int[] lefti = new int[nums.length]; 
        int[] righti = new int[nums.length]; 
        
        // 第一次遍历：计算左侧累积乘积
        for (int i = 0; i < nums.length; i++) {
            left *= nums[i];
            lefti[i] = left;
            
            // 第二次遍历：计算右侧累积乘积
            right *= nums[nums.length - i - 1];
            righti[nums.length - i - 1] = right;
        }
        
        // 根据左右累积乘积计算最终结果
        nums[0] = righti[1];
        nums[nums.length - 1] = lefti[nums.length - 2];
        for (int i = 1; i < nums.length - 1; i++) {
            nums[i] = lefti[i - 1] * righti[i + 1];
        }
        
        return nums;
    }
}