解題說明
Add to Array-Form of Integer
題目描述：
一個整數的「陣列形式」是由其每一位數字組成的陣列。例如 1234 的陣列形式為 [1, 2, 3, 4]。給定一個非負整數的陣列形式 num 和一個整數 k，返回 num + k 的陣列形式。
解題思路： 逐位相加法：
將 k 視為「進位」，從 num 的最低位開始，每一位加上 k 的當前最低位：
- 從
num的末尾開始向前遍歷。 - 每一步：
sum = num[i] + k % 10，k /= 10。 - 若有進位（
sum >= 10），加到k上：k += sum / 10，num[i] = sum % 10。 - 處理完
num後，若k > 0，繼續在前面插入k的各位數字。
C++ 解法
複雜度分析
時間複雜度：O(max(n, log k)) — 其中 n 是 num 的長度，log k 是 k 的位數。最差情況下需要處理兩者中較長的。
空間複雜度：O(1) — 原地修改 num（不計結果本身）。insert(begin) 操作每次 O(n)，總計最差 O(n * log k)；如果改用反轉則可避免。
虛擬碼
1. Set i = len(num) - 1. 2. While i >= 0 or k > 0: a. If i >= 0: k += num[i]. b. Set current digit = k % 10. c. k = k / 10. d. If i >= 0: num[i] = current digit, decrement i. e. Else: prepend current digit to num. 3. Return num.
其他解法
反轉 + 尾部追加：O(max(n, log k)) 時間、O(1) 額外空間。先反轉 num，逐位相加並在尾部追加（O(1) amortized），最後再反轉回來。避免了 insert(begin) 的 O(n) 開銷。
使用 deque：O(max(n, log k)) 時間、O(n) 空間。用雙端佇列存放結果，在前端插入為 O(1)。
延伸思考
insert(begin)操作的時間複雜度為什麼是 O(n)？如何用反轉技巧來避免？- 如果
k可能是負數（即做減法），演算法需要如何修改？ - 本題的逐位相加與「兩數之和的鏈表表示」（LeetCode 2）有何異同？