1480. Running Sum of 1d Array (一維數組的動態和)

閱讀時間約 1 分鐘


英文版點我中文版點我


↑看個小廣告,支持好內容↑



題目想輸出的是「從頭加到逐項的累積值」,走到哪就加到哪,其實就是我們常稱的 Prefix Sum,但該如何取得呢?


✖ 壞解法

// 每次都要從頭算起,雙重迴圈 O(n^2)

第一項=nums[0]
第二項=nums[0]+nums[1]
第三項=nums[0]+nums[1]+nums[2] ...


⭕ 好解法

// 保存了先前算到哪,每次往下加一項

第一項=nums[0]
第二項=第一項+nums[1]
第三項=第二項+nums[2] ...


第一項不動,往後算第 N 項時就去取第 N-1 項往下加,再寫入結果。附帶一提,雖然不太鼓勵,但這題要直接更新於原陣列 (In-place 修改) 也可行~


參考程式碼:

var runningSum = function(nums) {
// 原地修改
for(let i=1; i<nums.length; i++){
nums[i]+=nums[i-1];
}
return nums;

// 新陣列輸出
let arr=[nums[0]];
for(let i=1; i<nums.length; i++){
arr.push(arr[arr.length-1]+nums[i]);
}
return arr;
};



  • 本題分類標籤:ArrayPrefix Sum
  • 本題正解率=86.6%

❤️ 若內容對你實用,歡迎追蹤本專題,或小額贊助支持~
⭐ 這是我的第 12 篇刷題筆記,完整解題索引看這裡 → Here

54會員
59內容數
我要成為 LeetCode 王!快跟我一起踏上旅程!
留言0
查看全部
發表第一個留言支持創作者!
LeetCode King 的其他內容
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
只講得出一種做法就輸了!畫點文氏圖,幫你複習一下集合運算~
這道題你一定會解,但你知道怎麼把迴圈改寫成「迭代」嗎?這招學起來!
一串數字能夠組成等差數列嗎?有沒有不排列就能判斷的方法?
% 這個符號在 SQL 能做什麼,你都記得嗎?
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
只講得出一種做法就輸了!畫點文氏圖,幫你複習一下集合運算~
這道題你一定會解,但你知道怎麼把迴圈改寫成「迭代」嗎?這招學起來!
一串數字能夠組成等差數列嗎?有沒有不排列就能判斷的方法?
% 這個符號在 SQL 能做什麼,你都記得嗎?
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
端午要✈️去跑山了。剛看了一下自己ITRA的表現分,順便查了一下台灣跑越野跑的人有多少(正常大一點的比賽都有Itra認證)真的是出乎意料的少耶~
Thumbnail
我用了大約5套的跑步APP,這些APP分別是:RQ(Running Quotient)、TP(Training Peak)、Strava、Healthfit、Runalyze,每一套都有不一樣的用法。為什麼要用這麼多套跑步APP?
Thumbnail
上週六在丹麥哥本哈根開幕的國際性腦麻特殊自行車競賽 (Frame Running ) 在本週二已經圓滿結束,這場專門給這些勇敢的腦麻鬥士們的比賽讓他們有機會將平時努力訓練的成果在一年一度的競賽中展現出來。 開幕那天,麥先生和 Danielson 有幸到場參與並為台灣和來自16 個國家的選手們加油,
Thumbnail
第一篇我想談談韓國綜藝節目「Running man」,會先從這個節目開始,除了較為熟悉以外,主要是最近收看時,我有種很奇怪的感覺,並不只是策畫創意低潮,是有種氛圍的奇怪感,我想這幾週又突然興起的各種批判也是因為同樣感受到了這種奇怪。像是一種藏在檯面下的、卻無法忽略的東西,由於沒有被提出,很難明確確認
Thumbnail
我們說歷史都是注定的,不可能有意外,但偏偏有時候,這個意外就會發生。今天這個意外跟穿越時空有關,這件事在諸多古籍如《晉紀》、《幕府燕閑錄》、《北夢瑣言》等中都有記載,是一件載入史冊的穿越歷史事件。 夢溪筆談那是在公元383年,東晉淝水之戰的前夕,東晉劉牢之的部隊和前秦梁成的部隊隔著洛澗河對峙。
Thumbnail
2022/12/01 【今日交易】 今天軍工的二哥也被抓去關了,可想而知族群就會開始慢慢冷卻下來, 大家就往其他地方去關注,休息好一陣子安控族群又重新活了過來, 最近最猛的還有4979肯定是資金的聚集地, 還有化工後面走上來的生技,真的蠻多族群都有起色的, 今天比較可惜的就是,量比較大的一兩筆交易都
Thumbnail
搖搖晃晃的開著車在寶山路,隨機撥放的歌單放了一首Running On Faith。 「這才是最純真的抒情歌啊!」爸爸像是酒醒一般突兀地冒出一句話,我點點頭表示認同,看來父子倆都「很久」沒聽到這首歌,只是各自的久又是另一回事了。 我開始不專心的操控方向盤、油門,回憶不久之前的Running On Fa
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
端午要✈️去跑山了。剛看了一下自己ITRA的表現分,順便查了一下台灣跑越野跑的人有多少(正常大一點的比賽都有Itra認證)真的是出乎意料的少耶~
Thumbnail
我用了大約5套的跑步APP,這些APP分別是:RQ(Running Quotient)、TP(Training Peak)、Strava、Healthfit、Runalyze,每一套都有不一樣的用法。為什麼要用這麼多套跑步APP?
Thumbnail
上週六在丹麥哥本哈根開幕的國際性腦麻特殊自行車競賽 (Frame Running ) 在本週二已經圓滿結束,這場專門給這些勇敢的腦麻鬥士們的比賽讓他們有機會將平時努力訓練的成果在一年一度的競賽中展現出來。 開幕那天,麥先生和 Danielson 有幸到場參與並為台灣和來自16 個國家的選手們加油,
Thumbnail
第一篇我想談談韓國綜藝節目「Running man」,會先從這個節目開始,除了較為熟悉以外,主要是最近收看時,我有種很奇怪的感覺,並不只是策畫創意低潮,是有種氛圍的奇怪感,我想這幾週又突然興起的各種批判也是因為同樣感受到了這種奇怪。像是一種藏在檯面下的、卻無法忽略的東西,由於沒有被提出,很難明確確認
Thumbnail
我們說歷史都是注定的,不可能有意外,但偏偏有時候,這個意外就會發生。今天這個意外跟穿越時空有關,這件事在諸多古籍如《晉紀》、《幕府燕閑錄》、《北夢瑣言》等中都有記載,是一件載入史冊的穿越歷史事件。 夢溪筆談那是在公元383年,東晉淝水之戰的前夕,東晉劉牢之的部隊和前秦梁成的部隊隔著洛澗河對峙。
Thumbnail
2022/12/01 【今日交易】 今天軍工的二哥也被抓去關了,可想而知族群就會開始慢慢冷卻下來, 大家就往其他地方去關注,休息好一陣子安控族群又重新活了過來, 最近最猛的還有4979肯定是資金的聚集地, 還有化工後面走上來的生技,真的蠻多族群都有起色的, 今天比較可惜的就是,量比較大的一兩筆交易都
Thumbnail
搖搖晃晃的開著車在寶山路,隨機撥放的歌單放了一首Running On Faith。 「這才是最純真的抒情歌啊!」爸爸像是酒醒一般突兀地冒出一句話,我點點頭表示認同,看來父子倆都「很久」沒聽到這首歌,只是各自的久又是另一回事了。 我開始不專心的操控方向盤、油門,回憶不久之前的Running On Fa