解題說明
題目描述
給定一個陣列 nums，定義**執行和（Running Sum）**為 runningSum[i] = nums[0] + nums[1] + ... + nums[i]。
請回傳 nums 的執行和陣列。換言之，輸出陣列的第 i 個元素等於輸入陣列前 i+1 個元素的總和。
範例：
- 輸入：
nums = [1, 2, 3, 4] - 輸出：
[1, 3, 6, 10]
解題思路
核心概念：原地前綴和
這道題是前綴和最基礎、最直觀的形式。對於每個位置 i（從 1 開始），只需將前一個位置的值加到當前位置：
nums[i] += nums[i-1]
這樣 nums[i] 就從「原始值」變成「前 i+1 個元素的總和」，正好是所求的執行和。
為什麼能原地計算？ 因為計算 nums[i] 時，只依賴 nums[i-1]（已經是前 i 個元素的和），不需要之前更早的資訊。從左到右依序計算，每個位置只讀取一次前一個位置的值，沒有資料相依問題。
與標準前綴和的關係
標準前綴和通常定義 prefix[i] = nums[0] + ... + nums[i-1]（從 0 開始，長度為 n+1），而本題的執行和等同於「在原陣列上做 in-place 前綴和」，即 result[i] = nums[0] + ... + nums[i]（從 0 開始，長度為 n）。
兩者本質相同，只是索引偏移不同。理解這道題是掌握所有前綴和題目的起點。
C++ 解法
複雜度分析
時間複雜度
O(n)，其中 n 為陣列長度。只需從頭到尾遍歷一次陣列，每個元素執行一次加法運算。
空間複雜度
- 原地修改版：O(1) 額外空間（忽略輸出本身）。直接在輸入陣列上修改，不需要額外陣列。
- 新陣列版：O(n) 額外空間，用於儲存結果陣列。
若題目允許修改輸入陣列，原地版本是最佳選擇；若需保留原始陣列，則使用新陣列版本。
虛擬碼
1. For i from 1 to n-1: a. nums[i] = nums[i] + nums[i-1] 2. Return nums (Alternative with new array): 1. Create result array of size n 2. result[0] = nums[0] 3. For i from 1 to n-1: a. result[i] = result[i-1] + nums[i] 4. Return result
其他解法
替代方案
方案一：使用 partial_sum（STL 標準庫）
C++ STL 提供了 std::partial_sum 函式（定義於 <numeric>），可以直接計算前綴和：partial_sum(nums.begin(), nums.end(), result.begin())。
- 優點：一行程式碼，語義清晰，利用標準庫避免手寫迴圈。
- 缺點：需要熟悉 STL，且無法原地計算（輸入輸出若相同可能有未定義行為，需確認）；面試中手寫迴圈更能展示理解。
方案二：遞迴計算
將執行和定義為遞迴：runningSum(i) = runningSum(i-1) + nums[i]，以遞迴方式實作。
- 優點：完全符合數學定義，程式碼結構清晰。
- 缺點：有函式呼叫堆疊開銷，空間複雜度 O(n)（遞迴深度）。對大陣列可能有堆疊溢位風險，效率不如迭代版本。
方案三：scan（函式式風格）
使用函式式程式設計中的 scan 操作（類似 reduce 但保留所有中間結果），概念上與前綴和完全等價。Python 的 itertools.accumulate、Haskell 的 scanl1 都是此思路。
- 優點：在支援高階函式的語言中程式碼極為簡潔。
- 缺點：C++ 中無直接對應，需自行實作或使用
partial_sum，不如迴圈直觀。
延伸思考
延伸問題
-
區間和查詢：若在建立執行和之後，需要大量回答「
nums[left]到nums[right]的總和是多少」，執行和陣列如何幫助我們 O(1) 回答？（sumRange(l, r) = runningSum[r] - runningSum[l-1]，當 l > 0 時；注意 l=0 的邊界。） -
二維執行和：如何將此概念推廣到二維矩陣，計算每個
(i, j)點的「左上角矩形和」？這就是二維前綴和，用於 O(1) 回答任意子矩陣查詢（LC 304）。 -
差分陣列是前綴和的逆操作：執行和（前綴和）是累積加法，而差分陣列是它的逆——
diff[i] = nums[i] - nums[i-1]。對差分陣列做前綴和還原就能得到原始陣列。這個性質可用於高效率地對陣列區間進行批量加減操作（LC 370）。