题目链接

题目大意是给出一个已经按升序排列的由正整数组成的数组nums和一个正整数n,要求至少加入多少个数之后使得数组能通过相加形成[1,n]之间的所有数。

思路如下：假设miss是第一个不能通过当前部分数组生成的数，即现在能生成数的区间为[0,miss-1]。 考虑接下来nums提供的数num(如果存在的话)，可以通过在原区间的两端加上num生成一个新的区间[num,num+miss-1]。

  • 若num<=miss，则两个区间可合并为一个区间[0,num+miss-1]，num+miss成为新的miss
  • 若num>miss或者说原数组已经用完不能再提供num，则两个区间将不能合并，需加入一个数patch_num替代num使得两区间能合并，为使表示的范围尽量大应取这个数patch_num=miss, 这样便会得到一个新的可生成数的区间[0, miss+miss-1]，miss也会相应更新为miss+miss.

这样循环直到miss>n即可。

按照上面的思路，代码如下：

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