题目
给定一个已排序的正整数数组 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提示：
1 <= nums.length <= 10001 <= nums[i] <= 104nums按 升序排列1 <= n <= 231 - 1
解答
- 贪心算法
题目使用的是贪心算法。贪心算法的基本思想是，在每一步选择中都选择当前状态下最优的选择，以求得最终的全局最优解。
对于这道题，我们的贪心策略是在已经被覆盖的区间内，选择尽可能靠右的数字来扩展区间，这样可以让被覆盖的区间尽可能的大，从而让需要添加的数字的数量尽可能的少。
当遍历到一个数时，如果这个数小于等于 covered + 1，那么它可以被当前的区间所覆盖，因此可以将它加入到被覆盖的区间内，更新 covered 的值(covered += nums[i])。如果这个数大于 covered + 1，那么当前的区间无法覆盖它，因此需要添加一个新的数字，使得被覆盖的区间能够扩展到这个数，更新 covered 的值(covered += covered + 1)。
这个贪心策略的正确性可以通过反证法来证明：假设存在一个更优的解，使得需要添加的数字的数量比当前算法得到的解更少。那么这个更优的解必然包含一个数字 x，它是我们在当前算法中添加的数字。如果将 x 从更优的解中删除，那么这个解就会变成一个覆盖范围更小、需要添加的数字数量相同的解，与我们的假设矛盾。因此，当前算法得到的解就是最优解，贪心策略是正确的。
可以先求解所有需要被插入的数字，再返回拥有所有被插入数字的数组的长度，实现代码如下：
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
vector<int> patches; // 用于保存需要插入的数字
long long int covered = 0; //用longlong类型存储当前已经被覆盖的数的范围
int i = 0; //nums数组的下标
while (covered < n) { // 只要还没有覆盖到n，就需要添加数字
if (i < nums.size() && nums[i] <= covered + 1) {
// 如果nums[i]小于等于当前已经被覆盖的数的下一个数(covered + 1)
// 那么就可以将nums[i]加入到被覆盖的范围内
covered += nums[i];
i++;
} else {
// 如果nums[i]大于covered + 1, 那么就需要添加一个新的数字
int patch = covered + 1;
covered += patch;
patches.push_back(patch);
}
}
return patches.size();
}
};因为题目并没有要求存储被插入的数组，为了更低的空间占用，可以不存储要插入的数字，直接对计数器count自加一：
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
long long int covered = 0; // 用 long long 类型存储当前已经被覆盖的数的范围
int count = 0; // 记录需要添加的数字的数量
int i = 0; // nums 数组的下标
while (covered < n) { // 只要还没有覆盖到 n，就需要添加数字
if (i < nums.size() && nums[i] <= covered + 1) {
// 如果 nums[i] 小于等于当前已经被覆盖的数的下一个数（covered + 1）
// 那么就可以将 nums[i] 加入到被覆盖的范围内
covered += nums[i];
i++;
} else {
// 如果 nums[i] 大于 covered + 1，那么就需要添加一个新的数字
covered += covered + 1;
count++;
}
}
return count;
}
};