題目敘述 Patching Array
題目給定一個整數陣列，
請問還要補上多少個數字，才能用這些數字的和拼湊出所有1~n的整數。
測試範例
Example 1:
Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.
[1,2,3]可以拼出1~6地所以整數
1 = 1
2 = 2
3 = 3
4 = 3+1
5 = 3+2
6 = 3+2+1
Example 2:
Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].
[1,2,4,5,10] 可以拼出1~20地所以整數
1 = 1
2 = 2
3 = 2+1
4 = 4
5 = 5
6 = 5+1
7 = 5+2
8 = 5+2+1
9 = 5+4
10 = 10
11 = 10+1
12 = 10+2
13 = 10+2+1
14 = 10+4
15 = 10+4+1
16 = 10+5+1
17 = 10+5+2
18 = 10+5+2+1
19 = 10+5+4
20 = 10+5+4+1
Example 3:
Input: nums = [1,2,2], n = 5
Output: 0
[1,2,2] 可以拼出1~5地所以整數
1 = 1
2 = 2
3 = 2+1
4 = 2+2
觀察 湊整數的區間延伸
假設本來已經能湊出[1, x)的區間。
遇到新的數字y，假如y <= x 那麼可以延伸區間到[1, x+y)
只要把已知的方法再額外加上y即可。
遇到新的數字y，假如y > x ，代表需要補上一個新的數字x
補上新數字之後，可以延伸區間到[1, x+x) = [1, 2x)
接著再依循同樣的檢查邏輯，看看y 現在是 <= 2x 還是 > 2x。
最終，假如區間的終點x，已經大於n，代表我們可以用現有的數字做加法，湊出[1, n]區間內的所有整數。
示意圖
演算法 盡可能的延伸區間
承接觀察點的思考。
每遇到一個整數y，先確認是落在[1, x)區間內還是區間外。
落在區間內，就用現在這個整數去延伸區間到[1, x+y)
落在區間外，則補上一個整數x，延伸區間到[1, x+x) = [1, 2x)
接著再用同樣的規則檢查整數y
反覆迭代，一直到區間[1,x)能夠覆蓋n值為止。
程式碼 盡可能的延伸區間
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
# counting of patch, upper bound of coverage
patchCount, limit = 0, 1
# Initialization: we can cover interval [1, limit)
# Array index
index = 0
# Push limit to cross over n with minimal count of patches
while limit <= n:
if index < len(nums) and nums[index] <= limit:
# Now we can cover interval [1, limit + nums[index])
limit += nums[index]
index += 1
else:
# Current number is out of interval [1, limit)
# patch 'limit' into array, now we can cover interval [1, limit + limit) = [1, 2*limit]
patchCount += 1
limit *= 2
return patchCount
複雜度分析
時間複雜度: O( len(nums) + log n)
掃描每個陣列雲素耗費O( len(nums) )
延伸區間，直到覆蓋n為止，區間成長速度為兩倍，所需時間為O( log n)
空間複雜度: O(1)
所用到的都是固定尺寸的臨時變數，所需空間為O(1)
關鍵知識點
盡可能用最少的補充次數去延伸區間。(相當於貪心Greedy策略)
Reference:
[1] Patch Array
