330.md

#330. Patching Array 题目链接

public class Solution {
    public int minPatches(int[] nums, int n) {
        // 设置miss为缺失的数字，从1开始检查，检查从[1, miss]这个范围是否可以覆盖
        long miss = 1;
        int j = 0, result = 0;
        while (miss <= n) {
            // 如果nums[j]比miss小，说明能够覆盖到miss，那么就检查[1,miss+nums[j]}这个范围是否能覆盖
            // 这里的miss是指前j个数字的和，如果第j个数字比前j个数字的和还要小的话，说明能够覆盖到[nums[j],miss]这个范围
            // 因为数组是非递减的，而miss-nums[j]=miss[j-1]，miss[j]>=miss[j-1]，所以能够证明出可以覆盖到[nums[j],miss]这个范围
            if (j < nums.length && nums[j] <= miss) {
                miss += nums[j++];
            }
            // 如果nums[j]比miss大，说明无法覆盖到miss,miss是要补充的数字，所以miss自己加上自己
            else {
                miss += miss;
                result++;
            }
        }
        return result;
    }
}