循环不变量

• 概述

循环不变量是指在循环开始，循环过程中每一次迭代均为真的量。循环不变量被用来证明循环的正确性。

• 例题：按要求补齐数组

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
题目来源：Leetcode330题
题目链接：https://leetcode-cn.com/problems/patching-array
分析：

参考解答：

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