330. Patching Array

Leetcode link

解题思路

本题是个 hard。

题目给了我们两个参数：数组、一个数字 n。题目要求我们在给定数组中插入最少的数字让这个数组的元素能组合出 1～n 的数字

我们可以直接用一个例子来讲解：nums=[3, 5, 20]， n = 30

首先，我们需要一个变量来表示当前缺少的数，我们取名为 miss 并且初始值为 1

接着我们需要挨个比较 miss 与当前数组中的数字（用 i 作为数组遍历的下标），此时有两种情况：

1. miss < nums[i]：这种情况表示当前缺失的数字无法被数组中最小的数字补充，此时为了插入最少的数（最大化插入每个数的表示范围），我们应该插入一个 miss，此时的表达范围来到了 [0, miss*2)
2. miss >= nums[i]：这种情况表示当前数组中有比当前缺失数字小的数，如果把它加进来，我们的表达范围变成了 [0, miss+nums[i])

接下来我们需要做的就是遍历整个数组，直到 miss > n ，因为此时的可表示范围已经超过了 n（可表示范围来到了 [0, miss) ）

介绍完原理我们来过一次这个逻辑：

1. 一开始我们的 miss = 1，小于 n，于是我们遍历数组第一个元素 3，发现 miss < 3（情况 1），于是我们需要插入 1 到数组，此时我们的表示范围为 [0, 2) （2 代表 miss 2）（*注意右侧为开区间）
2. 此时 miss = 2，我们依然比较第一个元素 3，发现 miss < 3（情况 1），于是我们需要插入数字 2 到数组，此时我们的表示范围来到了 [0, 4) （4 代表 miss * 2）
3. 此时 miss = 4，我们依然比较第一个元素 3 ，发现 miss > 3（情况 2），于是我们把数组元素 3 加进来，此时我们的表示范围来到了 [0, 7) （7 代表 miss + 3）
4. 此时 miss = 7，我们比较数组的下一个元素 5，发现 miss > 5（情况 2），于是我们把数组元素 5 加进来，此时我们的表示范围来到了 [0, 12) （7 代表 miss + 5）
5. 此时 miss = 12，我们比较数组的下一个元素 20，发现 miss < 20（情况 1），于是我们需要插入 12 到数组，此时我们的表示范围为 [0, 24) （24 代表 miss * 2）
6. 此时 miss = 24，我们比较数组的当前元素 20，发现 miss > 20（情况 2），于是我们把数组元素 20 加进来，此时我们的表示范围来到了 [0, 44) （44 代表 miss + 20）
7. 此时我们数组能表示的范围已经超过了题目的 n，所以循环结束，回顾我们循环，发现只有情况 1 之下会需要插入新的数字到数组，而情况 1 出现了 3 次，所以我们的答案是 3

Javascript

/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number}
 */
var minPatches = function(nums, n) {
    let i = 0;
    let miss = 1;
    let result = 0;

    while(miss <= n) {
        if(i < nums.length && nums[i] <= miss) {
            miss += nums[i];
            i++;
        } else {
            miss += miss;
            result++;
        }
    }
    return result;
};