。修补阵列

330。修补数组

难

给定一个排序的整数数组 nums 和一个整数 n，向数组添加/修补元素，使得 [1, n] 范围内的任何数字都可以由数组中某些元素的总和形成。

返回所需的最小补丁数量.

示例1：

• 输入： nums = [1,3], n = 6
• 输出： 1
• 说明：
  • nums 的组合是 [1], [3], [1,3]，形成可能的和：1, 3, 4。
  • 现在，如果我们向 nums 添加/修补 2，则组合为：[1], [2], [3], [1,3], [2,3], [1,2,3]。
  • 可能的和是 1, 2, 3, 4, 5, 6，现在涵盖范围 [1, 6]。
  • 所以我们只需要 1 个补丁。

示例2：

• 输入： nums = [1,5,10], n = 20
• 输出： 2
• 说明： 两个 patch 可以是 [2, 4]。

示例3：

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

限制：

• 1
• 1 4
• nums 按升序排列.
• 1 31 - 1

解决方案：

联系链接

• 领英
• GitHub

以上是。修补阵列的详细内容。更多信息请关注PHP中文网其他相关文章！