LeetCode 筆記 - 494. Target Sum
題目在此 494. Target Sum
給定一個整數陣列 nums 與一個目標值 target。
請找出有多少種方法可以對 nums 中的每個元素加上正號或負號,使得最終的總和等於 target。
例如:1
2
3
4
5
6
7
8Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
解題思維
這題我們可以使用動態規劃(Dynamic Programming)來解決。
關鍵在於我們需要考慮每個數字可以有兩種選擇:
- 加上正號
- 加上負號
我們定義一個 dp 陣列,其中 dp[i] 是一個字典(或 Counter),用來記錄使用前 i 個數字可以達成的所有可能總和及其對應的方法數量。
具體來說,對於每個數字 nums[i],我們可以從前一個狀態 dp[i - 1] 中的每一個產生出的總和 k 出發,計算出兩個新的總和:k + nums[i] 和 k - nums[i],並將這兩個總和的方法數量累加到 dp[i] 中。
Time complexity 是 $O(n * sum(nums))$
其中 n 是陣列的長度,sum(nums) 是陣列中所有數字的總和。這是因為我們每次都是在 $sum(nums)$ 的範圍中搜尋答案,而我們需要對每個數字都進行這樣的操作 (n 次)。
Space complexity 是 $O(sum(nums))$,因為我們需要存儲所有可能的總和及其對應的方法數量。
程式碼
1 | class Solution: |