【LeetCode】按要求补齐数组 [H]（贪心）

330. 按要求补齐数组 - 力扣（LeetCode）

一、题目

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

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

示例 1：
输入: nums = [1,3], n = 6
输出: 1 
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。

示例 2：
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2,4]。

示例 3：
输入: nums = [1,2,2], n = 5
输出: 0

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• nums 按 升序排列
• 1 <= n <= 231 - 1

二、代码

class Solution {
    public int minPatches(int[] nums, int n) {
        int N = nums.length;
        Arrays.sort(nums);
        // 这里要用long，因为累加和有可能超过int型范围，造成溢出
        // 凡是累加和的一定要留意累加和类型是否会溢出
        // 表示此时已经可以推出1~range范围的累加和了
        long range = 0;
        // 额外补充的数字个数
        int cnt = 0;
        // 遍历到的数组位置
        int i = 0;
        // 开始遍历数组
        while (i < N) {
            // 如果此时已经能退出来1~n的范围了，直接返回
            if (range >= n) {
                return cnt;
            }
            // 如果nums[i] <= range + 1，说明此时可以直接使用数组中已有的nums[i]来推高累加和范围，能够保证不遗漏累加和
            if (nums[i] <= range + 1) {
                // 推高累加和范围，就是直接加上nums[i]
                range += nums[i];
                // 继续向后遍历
                i++;
            // 如果此时nums[i]还不能直接用，就需要先补充一些数，使nums[i] <= range + 1条件成立后才可以用nums[i]
            } else {
                // 补充range+1这个数，能够最大限度地推高累加和范围，这样能够使额外补充的数最少。
                range += (range + 1);
                // 额外补充的数量加1
                cnt++;
            }
 
        }
        
        // 如果数组遍历完了，还是没有达到要求，后面就全部由补充的数来推高范围
        // 让range>=n时，就符合条件了，返回答案
        while (range < n) {
            // 全都补充range+1，最大限度地推高累加和范围，这样能够使额外补充的数最少。
            range += (range + 1);
            // 额外补充的数量加1
            cnt++;
        }
        // 返回答案
        return cnt;
    }
}

三、解题思路 

看数组上的数字能不能用，就是看此时已经能求出来0~a了，a就是已经能求出来的范围边界，假设此时判断的数字是b，只有当b <= a + 1成立，才可以使用b，否则直接使用b就会遗漏一些累加和。