Patching Array

此题就是Elements of interview里面的那道constructable range，重点在于这里有一个数学规律存在，即假设前i个数之间的任意组合可以覆盖1-k范围内的任何数，则这里的k肯定是前面i个数的和，如果第i + 1个数加进这个序列之后还能覆盖到1-k+nums[i+1]这个范围，则nums[i+1]这个数是不可能大过k + 1的，这个数学证明是不懂，但是你随便拿几组数试试就知道确实是这样，这道题就是利用了这个解题思路，维护一个cumSum，如果当前数组元素大于cumSum + 1，则我们把cumSum加上cumSum + 1这个值，同时指针停留在当前位置再比较，知道cumSum + 1大于等于当前元素了，我们就把当前元素加上同时继续前进，直到我们的cumSum这个值大于等于n为止

class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        cumSum = 0
        result = 0
        cur = 0
        length = len(nums)

        while cumSum < n:
            if cur < length and cumSum + 1 >= nums[cur]:
                cumSum += nums[cur]
                cur += 1
            else:
                result += 1
                cumSum += (cumSum + 1)

        return result