โปรแกรมหาผลรวมสะสม (Running Sum) ของอาร์เรย์ 1 มิติใน Python

ภาพรวม

Running Sum rs[i] คือผลรวมของสมาชิกตั้งแต่ nums[0] ถึง nums[i] ต้องการคืนค่าอาร์เรย์ Running Sum ทั้งหมด

ตัวอย่าง

nums = [8,3,6,2,1,4,5]

Running Sum: [8, 11, 17, 19, 20, 24, 29]

ขั้นตอนการแก้ปัญหา

1. ตั้งค่า n = len(nums), rs = [nums[0]]
2. วนลูป i จาก 1 ถึง n-1:
   • nums[i] += nums[i-1] (อัปเดตค่าสะสมในตัว)
   • rs.append(nums[i])
3. คืนค่า rs

ตัวอย่างโค้ด (Python)

def solve(nums):
    n = len(nums)
    rs = [nums[0]]
    for i in range(1, n):
        nums[i] += nums[i-1]
        rs.append(nums[i])
    return rs

nums = [8,3,6,2,1,4,5]
print(solve(nums))

อินพุต

[8,3,6,2,1,4,5]

เอาต์พุต

[8, 11, 17, 19, 20, 24, 29]

วิธีทางเลือก (itertools.accumulate)

from itertools import accumulate
def solve_alt(nums):
    return list(accumulate(nums))

ความซับซ้อน

• เวลา: O(n)
• พื้นที่: O(n) สำหรับผลลัพธ์ (O(1) เพิ่มเติมถ้าแก้ไขในตัว)