330. 按要求补齐数组

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 1:

输入: nums = [1,3], n = 6
输出: 1
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。
示例 2:

输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:

输入: nums = [1,2,2], n = 5
输出: 0

思路

！注意下方集合的开闭情况。

定义miss变量，里面存的值是在[0,n)中可能需要补齐的那个数。这意味着，我们已经可以构建[0,miss)的之间的任何数了。

由此，

1. 如果给出的数组的下一个数是小于或者等于miss的，可以直接加在miss上，得到完整的不需要补齐的[0,miss+nums[0])。
2. 如果下一个数大于miss，那么我们需要补全的数是miss，所以添加miss这一个数，add+=1。现在，我们的完整的不需要补足的数组就变成了[0,miss]，而miss最多可以与miss-1相加，由此，我们的完整的不需要补足的数组就变成了[0,2*miss)
3. 如此循环，直到miss的值大于目标值。

TIPS：需要注意，不能使用int，会溢出，需使用long。

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