[LeetCode] Product of Array Except Self 除本身之外的數組之積

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

Solve it without division and in O(n).

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

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

這道題給定我們一個數組，讓我們傳回一個新數組，對于每一個位置上的數是其他位置上數的乘積，并且限定了時間複雜度O(n)，并且不讓我們用除法。如果讓用除法的話，那這道題就應該屬于Easy，因為可以先周遊一遍數組求出所有數字之積，然後除以對應位置的上的數字。但是這道題禁止我們使用除法，那麼我們隻能另辟蹊徑。我們想，對于某一個數字，如果我們知道其前面所有數字的乘積，同時也知道後面所有的數乘積，那麼二者相乘就是我們要的結果，是以我們隻要分别建立出這兩個數組即可，分别從數組的兩個方向周遊就可以分别建立出乘積累積數組。參見代碼如下：

C++ 解法一：

Java 解法一：

我們可以對上面的方法進行空間上的優化，由于最終的結果都是要乘到結果res中，是以我們可以不用單獨的數組來儲存乘積，而是直接累積到res中，我們先從前面周遊一遍，将乘積的累積存入res中，然後從後面開始周遊，用到一個臨時變量right，初始化為1，然後每次不斷累積，最終得到正确結果，參見代碼如下：

C++ 解法二：

Java 解法二：