# 330. 按要求补齐数组
### 题目地址(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
```
### 前置知识
* 贪心
* 前缀和
### 公司
* 暂无
### 思路
这道题核心点正如标题所言： **贪心** + **维护端点信息**。
贪心的思想这里不多说了，思路和[官方题解](https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/)是一样的。
先不考虑需要增加数字的情况，即没有任何缺失的数字。
这里给了几个例子方便大家理解。
> 左侧是 nums 数组， 右侧是 nums 可以覆盖的区间 \[start, end] （注意是左右都闭合）。当然如果你写出别的形式，比如左闭右开，那么代码要做一些调整。
\[1] -> \[1,1] \[1,2] -> \[1,3] \[1,2,3] -> \[1,6] \[1,2,3,4] -> \[1,10]
可以看出，可以覆盖的区间，总是 \[1, x] ，其中 x 为 nums 的和。
接下来，我们考虑有些数字缺失导致无法覆盖的情况。
算法：
1. 初始化覆盖区间为 \[0, 0] 表示啥都没覆盖，目标区间是 \[1, n]
2. 如果数组当前数字无法达到前缀和，那么需要补充数字，更新区间为 \[1, 前缀和]。
3. 如果数组当前数字无法达到前缀和，则什么都不需要做。
那么第二步补充数字的话需要补充什么数字呢？如果当前区间是 \[1,x]，我们应该添加数字 x + 1，这样可以覆盖的区间为 \[1,2\*x+1]。如果你选择添加小于 x + 1 的数字，达到的效果肯定没这个区间大。而如果你选择添加大于 x + 1 的数字，那么会导致 x + 1 无法被覆盖。这就是贪心的思想。
### 关键点解析
* 维护端点信息，并用前缀和更新区间
### 代码
代码变量说明：
* furthest 表示区间右端点
* i 表示当前遍历到的数组索引
* ans 是需要返回的答案
```py
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
furthest = i = ans = 0
while furthest < n:
# 可覆盖到，直接用前缀和更新区间
if i < len(nums) and nums[i] <= furthest + 1:
furthest += nums[i] # [1, furthest] -> [1, furthest + nums[i]]
i += 1
else:
# 不可覆盖到，增加一个数 furthest + 1，并用前缀和更新区间
# 如果 nums[i] > furthest + 1，说明我们必须添加一个数 x，其中 1 <= x <= furthest + 1，从贪心的角度我们应该选择 furthest + 1，这在前面已经讲过
furthest = 2 * furthest + 1 # [1, furthest] -> [1, furthest + furthest + 1]
ans += 1
return ans
```
如果你的区间信息是左闭右开的，代码可以这么写：
```py
class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
furthest, i, ans = 1, 0, 0
# 结束条件也要相应改变
while furthest <= n:
if i < len(nums) and nums[i] <= furthest:
furthest += nums[i] # [1, furthest) -> [1, furthest + nums[i])
i += 1
else:
furthest = 2 * furthest # [1, furthest) -> [1, furthest + furthest)
ans += 1
return ans
```
**复杂度分析**
* 时间复杂度：$O(N)$。
* 空间复杂度：$O(1)$。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/330.patching-array.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.