[LeeCode238] Product of Array Ex

Description：

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

• Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

题目描述：

• 给定一个数组，对数组中的每个元素求除自身外的其他元素的乘积
• 比如：给定 [1,2,3,4], 返回结果 [24,12,8,6].

注意事项：

1. 不能使用除法
2. 使用固定的额外空间
3. O(n)效率

思考过程：

1. 如果题目没有加O(n)条件的话，可以使用循环嵌套暴力求解，但是效率非常低
2. 如果没有限制不能使用除法，可以先循环一次计算所有元素乘积，再次循环用乘积去除当前元素再进行替换，这样就非常简单，但是可能存在值为0的元素，这时候需要区分对待
   • 当没有0的时候，直接进行除就可以了。
   • 当只有一个0的时候，为0的那位元素替换为其他元素的乘积，其他元素替换为0。
   • 当0的数量大于等于2的时候，排除任何一个元素都会存在与0相乘的情况，所以全部替换为0即可。
3. 加上以上两个条件之后，需要重新考虑了。可以想到，每个位置的元素结果应该为其左侧所有元素乘积再乘其右侧所有元素乘积，所以现在需要考虑如何分别获取并储存每个元素两侧元素的乘积结果。

代码：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int N = nums.length;
        int[] res = new int[N];   //创建一个额外空间，用于存储获取到的两侧元素乘积结果

        int l = 1;
        for(int i = 0; i < N ; i++){  //先进行循环，获取每个元素左侧元素的乘积
            res[i] = l;   //l用于保存每个元素左侧元素乘积结果
            l *= nums[i];   //获取下一次需要的值
        }
       
        int r = 1;
        for(int i = N-1; i >= 0 ; i--){   //再次循环，获取当前位置对应元素的右侧元素乘积，然后把获取到的结果进行修改
            res[i] *= r;   //r值用于保存每个元素右侧的元素乘积，本身res最后一位就是
            r *= nums[i];   //获取到乘积之后进行修改
        }
        return res;  //返回最终结果
    }
}