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;}
}