題目連結:
題目意譯:
你被給定一個長度為 n 的整數陣列 coins,其代表著你所擁有的 n 枚硬幣。第 i 枚硬幣的幣值為 coins[i]。如果你選定某幾枚硬幣之後的幣值總和為 x,則你可以湊出 x 這個金額值。
回傳從 0(包含)開始,你最大可以連續湊出多少個整數作為金額值。
注意到你可能會擁有多個幣值相同的硬幣。
限制:
coins.length == n
1 ≦ n ≦ 4 × 10 ^ 4
1 ≦ coins[i] ≦ 4 × 10 ^ 4
範例測資:
範例 1:
輸入: coins = [1,3]
輸出: 2
解釋: 你可以湊出以下數值:
- 0:拿 []
- 1:拿 [1]
你從 0 開始可以湊出連續 2 個整數值。
範例 2:
輸入: coins = [1,1,1,4]
輸出: 8
解釋: 你可以湊出以下數值:
- 0:拿 []
- 1:拿 [1]
- 2:拿 [1,1]
- 3:拿 [1,1,1]
- 4:拿 [4]
- 5:拿 [4,1]
- 6:拿 [4,1,1]
- 7:拿 [4,1,1,1]
你從 0 開始可以湊出連續 8 個整數值。
範例 3:
輸入: nums = [1,4,10,3,1]
輸出: 20
解題思維:
其實跟
這題基本上一樣,只是該題是問「最小無法被湊出的數字」,而本題是該數字的「前一個數字」。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。