↑看個小廣告,支持好內容↑
題目想輸出的是「從頭加到逐項的累積值」,走到哪就加到哪,其實就是我們常稱的 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;
};
Array
、Prefix Sum
86.6%
❤️ 若內容對你實用,歡迎追蹤本專題,或小額贊助支持~
⭐ 這是我的第 12 篇刷題筆記,完整解題索引看這裡 → Here