---

前言

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/patching-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

先给数组排序
range代表已经凑出来的数
如果range+1 那么我们只需在range的基础上加一个range+1,直到凑出arr[i]

如果已经凑出arr[i],则在range上加上arr[i]

如果已经遍历完arr,还没有凑出aim,
则不断在range的基础上加range+1,直到凑出aim

代码

class Solution {
    public int minPatches(int[] arr, int aim) {
        int ans=0;
        long range=0;
        Arrays.sort(arr);
        for(int i=0;i<arr.length;i++){
            //要求没被满足
            while(arr[i]-1>range){
                range+=range+1;
                ans++;
                if(range>=aim){
                    return ans;
                }
            }
            range+=arr[i];
            if(range>=aim){
                return ans;
            }
        }
        while(range+1<=aim){
            range+=range+1;
            ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26