330.按要求补齐数组

链接：330.按要求补齐数组
难度：Hard
标签：贪心、数组
简介：给定一个已排序的正整数数组 nums，和一个正整数  n 。从  [1, n]  区间内选取任意个数字补充到  nums  中，使得  [1, n]  区间内的任何数字都可以用  nums  中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

题解 1 - typescript

• 编辑时间：2020-12-29
• 执行用时：88ms
• 内存消耗：40.4MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/)。

function minPatches(nums: number[], n: number): number {
  let patches = 0;
  let x = 1;
  const len = nums.length;
  let i = 0;
  while (x <= n) {
    if (i < len && nums[i] <= x) {
      x += nums[i];
      i++;
    } else {
      x *= 2;
      patches++;
    }
  }
  return patches;
}