# 0238. 除自身以外數組的乘積 ## 題目地址（238. 除自身以外數組的乘積） <https://leetcode-cn.com/problems/product-of-array-except-self/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個長度為 n 的整數數組 nums，其中 n > 1，返回輸出數組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。 示例: 輸入: [1,2,3,4] 輸出: [24,12,8,6] 提示：題目數據保證數組之中任意元素的全部前綴元素和后綴（甚至是整個數組）的乘積都在 32 位整數范圍內。 說明: 請不要使用除法，且在 O(n) 時間復雜度內完成此題。 進階： 你可以在常數空間復雜度內完成這個題目嗎？（ 出于對空間復雜度分析的目的，輸出數組不被視為額外空間。） ``` ``` ## 前置知識 - 數組 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題的意思是給定一個數組，返回一個新的數組，這個數組每一項都是其他項的乘積。 符合直覺的思路是兩層循環，時間復雜度是O(n^2),但是題目要求`Please solve it without division and in O(n)`。 因此我們需要換一種思路，由于輸出的每一項都需要用到別的元素，因此一次遍歷是絕對不行的。 考慮我們先進行一次遍歷， 然后維護一個數組，第i項代表前i個元素（不包括i）的乘積。 然后我們反向遍歷一次，然后維護另一個數組，同樣是第i項代表前i個元素（不包括i）的乘積。  有意思的是第一個數組和第二個數組的反轉（reverse）做乘法（有點像向量運算）就是我們想要的運算。 其實我們進一步觀察，我們不需要真的創建第二個數組（第二個數組只是做中間運算使用），而是直接修改第一個數組即可。 ## 關鍵點解析 - 兩次遍歷， 一次正向，一次反向。 - 維護一個數組，第i項代表前i個元素（不包括i）的乘積 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @return {number[]} */</span> <span class="hljs-keyword">var</span> productExceptSelf = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>, temp = <span class="hljs-params">1</span>; i < nums.length; i++) { ret[i] = temp; temp *= nums[i]; } <span class="hljs-title">// 此時ret[i]存放的是前i個元素相乘的結果(不包含第i個)</span> <span class="hljs-title">// 如果沒有上面的循環的話，</span> <span class="hljs-title">// ret經過下面的循環會變成ret[i]存放的是后i個元素相乘的結果(不包含第i個)</span> <span class="hljs-title">// 我們的目標是ret[i]存放的所有數字相乘的結果(不包含第i個)</span> <span class="hljs-title">// 因此我們只需要對于上述的循環產生的ret[i]基礎上運算即可</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = nums.length - <span class="hljs-params">1</span>, temp = <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { ret[i] *= temp; temp *= nums[i]; } <span class="hljs-keyword">return</span> ret; }; ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的LeetCode題解