class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;//一维数组 answer[]存储最终的结果//首先从左往右记录乘积,暂时存储到一维数组 answer[] 中int[] answer = new int[length];//先从左往右, 由于由于第一个元素左边没有元素,所以需要初始化 answer[0] = 1answer[0] = 1;for(int i = 1; i < length; i++) { //i从1开始遍历是因为answer[0]已经被固定为1了// i 位置上左边所有元素的乘积如何而来?// answer[i]代表 i 左侧所有元素的乘积(乘到nums[i-1]), //那么 answer[i - 1] 是 i-1 左侧所有元素的乘积(乘到nums[i-2]),//再乘以nums[i - 1]就得到answer[i]answer[i] = nums[i - 1] * answer[i - 1]; }//此时answer[i] 存储的是 i 之前所有元素的乘积//然后我们更新右侧乘积, R 代表不同元素右侧所有元素的乘积值int R = 1; //(i = length - 1)时 i 右侧所有元素的乘积值 R, 也是 R 的初始值for(int i = length - 1; i >= 0; i--) { //为什么是i>=0而不是i>0?//此时 answer[i] 代表 i 左侧所有元素的乘积, 乘以 i 右侧所有元素的乘积值 R 得到结果//此时 R 代表 nums[i + 1] 连乘到 nums[length - 1](i=length - 1时除外)answer[i] = answer[i] * R; //更新 R, 相当于 R 往左前进一步, 进入下一次循环前 i 会减 1, 相当于 answer 数组左退一步。R = R * nums[i]; // 此时 R 才代表 nums[i] 连乘到 nums[length - 1] }return answer;}
}
关于这一部分的代码,为什么循环中的终止判断条件是i >= 0,当设置i > 0会得到错误的结果。
int R = 1;
for (int i = length - 1; i >= 0; i--) {// Multiply answer[i] (product of elements to the left) by R (product of elements to the right)answer[i] = answer[i] * R;// Update R to include nums[i]R *= nums[i];
}
i >= 0
是必须的,因为数组的第一个元素(nums[0]
)同样需要乘上右侧的乘积。- 如果终止条件设置为
i > 0
,那么i = 0
的位置就没有被处理,从而导致错误结果。