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

英文版點我｜中文版點我

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

✖ 壞解法

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

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

⭕ 好解法

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

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

第一項不動，往後算第 Ｎ 項時就去取第 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