1.题目基本信息

1.1.题目描述

给定一个已排序的正整数数组 nums ，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。

请返回 满足上述要求的最少需要补充的数字个数 。

1.2.题目地址

https://leetcode.cn/problems/patching-array/description/

2.解题方法

2.1.解题思路

贪心

2.2.解题步骤

第一步，构建维护变量。s维护当前遍历的区域中能够覆盖的范围[0,s-1]；i维护nums的遍历指针；result维护结果变量。

第二步，遍历nums，在s<=n的情况下，即覆盖范围还没有达到[1,n]的情况下，进行更新维护变量。

• 2.1.nums[i]<=s的情况，此时覆盖范围可以增加[nums[i],nums[i]+s-1]的覆盖区间，所以更新s进行覆盖区间扩展，并右移nums的指针（大于s时扩展会导致s不在覆盖区间中）

• 2.2.nums[i]>s的情况，此时为了让s在覆盖区间中，可以贪心的添加s到数组中进行范围扩展；并更新s和结果变量

第三步，返回结果变量

3.解题代码

python代码

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        # 思路：贪心
        # 第一步，构建维护变量。s维护当前遍历的区域中能够覆盖的范围[0,s-1]；i维护nums的遍历指针；result维护结果变量。
        result, s, i = 0, 1, 0
        # 第二步，遍历nums，在s<=n的情况下，即覆盖范围还没有达到[1,n]的情况下，进行更新维护变量。
        while s <= n:
            if i < len(nums) and nums[i] <= s:
                # 2.1.nums[i]<=s的情况，此时覆盖范围可以增加[nums[i],nums[i]+s-1]的覆盖区间，所以更新s进行覆盖区间扩展，并右移nums的指针（大于s时扩展会导致s不在覆盖区间中）
                s += nums[i]
                i += 1
            else:
                # 2.2.nums[i]>s的情况，此时为了让s在覆盖区间中，可以贪心的添加s到数组中进行范围扩展；并更新s和结果变量
                s += s
                result += 1
        # 第三步，返回结果变量
        return result

4.执行结果