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.)

題目描述：

• 給定一個(gè)數(shù)組，對(duì)數(shù)組中的每個(gè)元素求除自身外的其他元素的乘積
• 比如：給定 [1,2,3,4], 返回結(jié)果 [24,12,8,6].

注意事項(xiàng)：

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

思考過程：

1. 如果題目沒有加O(n)條件的話，可以使用循環(huán)嵌套暴力求解，但是效率非常低
2. 如果沒有限制不能使用除法，可以先循環(huán)一次計(jì)算所有元素乘積，再次循環(huán)用乘積去除當(dāng)前元素再進(jìn)行替換，這樣就非常簡(jiǎn)單，但是可能存在值為0的元素，這時(shí)候需要區(qū)分對(duì)待
   • 當(dāng)沒有0的時(shí)候，直接進(jìn)行除就可以了。
   • 當(dāng)只有一個(gè)0的時(shí)候，為0的那位元素替換為其他元素的乘積，其他元素替換為0。
   • 當(dāng)0的數(shù)量大于等于2的時(shí)候，排除任何一個(gè)元素都會(huì)存在與0相乘的情況，所以全部替換為0即可。
3. 加上以上兩個(gè)條件之后，需要重新考慮了?？梢韵氲?，每個(gè)位置的元素結(jié)果應(yīng)該為其左側(cè)所有元素乘積再乘其右側(cè)所有元素乘積，所以現(xiàn)在需要考慮如何分別獲取并儲(chǔ)存每個(gè)元素兩側(cè)元素的乘積結(jié)果。

代碼：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int N = nums.length;
        int[] res = new int[N];   //創(chuàng)建一個(gè)額外空間，用于存儲(chǔ)獲取到的兩側(cè)元素乘積結(jié)果

        int l = 1;
        for(int i = 0; i < N ; i++){  //先進(jìn)行循環(huán)，獲取每個(gè)元素左側(cè)元素的乘積
            res[i] = l;   //l用于保存每個(gè)元素左側(cè)元素乘積結(jié)果
            l *= nums[i];   //獲取下一次需要的值
        }
       
        int r = 1;
        for(int i = N-1; i >= 0 ; i--){   //再次循環(huán)，獲取當(dāng)前位置對(duì)應(yīng)元素的右側(cè)元素乘積，然后把獲取到的結(jié)果進(jìn)行修改
            res[i] *= r;   //r值用于保存每個(gè)元素右側(cè)的元素乘積，本身res最后一位就是
            r *= nums[i];   //獲取到乘積之后進(jìn)行修改
        }
        return res;  //返回最終結(jié)果
    }
}