What is the key greedy insight in Patching Array?

The smallest missing sum 'miss' should be added whenever the next array element is larger, as it maximally increases coverage without extra patches.

Can subset sums be precomputed to solve this problem?

Precomputing all subset sums is inefficient for large n; using greedy plus invariant tracking is much faster and avoids exponential computation.

How do we know the number of patches is minimal?

Each patch directly addresses the smallest missing sum, ensuring that each addition covers the largest possible new range and no redundant patches occur.

Does the array need to remain sorted after patching?

Sorting is not strictly required after each patch, but processing in order simplifies maintaining the invariant and implementing the greedy approach.

Is Patching Array always solved with greedy plus invariant validation?

Yes, this pattern ensures minimal patches efficiently and is the standard approach for the problem, handling all edge cases and large n.

#330

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

按要求补齐数组

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

数组贪心

题目描述

给定一个已排序的正整数数组 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 <= 1000
1 <= nums[i] <= 10⁴
nums 按 升序排列
1 <= n <= 2³¹ - 1

lightbulb

解题思路

方法一：贪心

我们假设数字 $x$ 是最小的不能表示的正整数，那么 $[1,..x-1]$ 的这些数都是可以表示的。为了能表示数字 $x$ ，我们需要添加一个小于等于 $x$ 的数：

如果添加的数等于 $x$ ，由于 $[1,..x-1]$ 的数都可以表示，添加 $x$ 后，区间 $[1,..2x-1]$ 内的数都可以表示，最小的不能表示的正整数变成了 $2x$ 。
如果添加的数小于 $x$ ，不妨设为 $x'$ ，由于 $[1,..x-1]$ 的数都可以表示，添加 $x'$ 后，区间 $[1,..x+x'-1]$ 内的数都可以表示，最小的不能表示的正整数变成了 $x+x' \lt 2x$ 。

因此，我们应该贪心地添加数字 $x$ ，这样可以覆盖的区间更大。

我们用一个变量 $x$ 记录当前不能表示的最小正整数，初始化为 $1$ ，此时 $[1,..x-1]$ 是空的，表示当前没有任何数可以被覆盖；用一个变量 $i$ 记录当前遍历到的数组下标。

循环进行以下操作：

如果 $i$ 在数组范围内且 $nums[i] \le x$ ，说明当前数字可以被覆盖，因此将 $x$ 的值加上 $nums[i]$ ，并将 $i$ 的值加 $1$ 。
否则，说明 $x$ 没有被覆盖，因此需要在数组中补充一个数 $x$ ，然后 $x$ 更新为 $2x$ 。
重复上述操作，直到 $x$ 的值大于 $n$ 。

最终答案即为补充的数的数量。

时间复杂度 $O(m + \log n)$ ，其中 $m$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        x = 1
        ans = i = 0
        while x <= n:
            if i < len(nums) and nums[i] <= x:
                x += nums[i]
                i += 1
            else:
                ans += 1
                x <<= 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(m + log n) where m is the length of nums and log n accounts for patches, since each patch doubles the reachable sum. Space complexity is O(1) extra space, using only variables to track coverage and patch count.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if candidates understand the greedy invariant principle in sum coverage.
question_mark
Listen for reasoning about why adding the smallest missing number extends coverage optimally.
question_mark
Observe if they track 'miss' correctly and iterate efficiently without recalculating sums.

warning

常见陷阱

外企场景

error
Trying to test all subset sums explicitly, which is too slow for large n.
error
Failing to update 'miss' correctly after adding a patch, leading to incorrect counts.
error
Assuming adding any number works rather than the minimal missing number, causing suboptimal patching.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to track which specific numbers need patching, not just the count.
arrow_right_alt
Restrict patches to only odd numbers or powers of two, testing adaptation of the greedy strategy.
arrow_right_alt
Ask for the maximum sum achievable with a fixed number of patches instead of minimal patch count.

help

常见问题

外企场景

继续练习

#334 递增的三元子序列 #324 摆动排序 II #321 拼接最大数