330. Patching Array

Given a sorted positive integer arraynumsand an integern, add/patch elements to the array such that any number in range[1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums=[1, 3],n=6
Return1.

Combinations ofnumsare[1], [3], [1,3], which form possible sums of:1, 3, 4.
Now if we add/patch2tonums, the combinations are:[1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are1, 2, 3, 4, 5, 6, which now covers the range[1, 6].
So we only need1patch.

Example 2:
nums=[1, 5, 10],n=20
Return2.
The two patches can be[2, 4].

Example 3:
nums=[1, 2, 2],n=5
Return0.

S： greedy

注意原数组是排好序的，由原数组可以得到当前的sum数组，从1开始找到sum数组第一个缺失的数字miss。不需要求出sum数组，利用排序数组的特性可以找到每个miss.假设当前可能的缺失数字为miss，

• 若nums[i] <= miss，因为[1, miss)全部存在，可用它来构建sum数组[1, miss + num[i])
• 若nums[i] > miss, 则miss一定缺失，因为[1,miss)全部存在于sum数组中，若在数组中加入miss，则[1+miss, miss + miss)全部在sum数组中即[1, miss + miss)全部cover。

    int minPatches(vector<int>& nums, int n) {
        long miss = 1, count = 0, i = 0;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                count++;
            }
        }
        return count;
    }