题目描述

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

 

题目大意

给定一个有序正整数数组和一个正整数n，要求将该数组内的数字随意组合，使其组合的数字之和满足在区间[1,n]之内，若所有的可能的组合之和缺少中的任意一个数字[1,n]，则需要在数组中添加一个数字或多个数字，使得新的数组的各个数字的组合的和将[1,n]中的所有数字都包含，求可能添加的最少的数字的个数。

 

示例

E1

Input: nums = [1,3], n = 6
Output: 1 
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, which now covers the range [1, 6].
So we only need 1 patch.

E2

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

E3

Input: nums = [1,2,2], n = 5
Output: 2
Explanation: The two patches can be [2, 4].

 

解题思路

学习了LeetCode@StefanPochmann的想法，若数组中的数字的组合之和可以满足[1,k]的组合，下一个数字为x

a. 若x小于k则无需加入新的数字，因为之前所有的数字已经可以满足到k的情况；

b. 若x大于k则需要加入新的数字，因为[k,x]之间的数字无法被组合出来，只需要加入数字x即可，加入数字数加一。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long mark = 1, res = 0, i = 0;
        while(mark <= n) {
            // 若当前的数字小于可得到的最大的数字，则更新mark
            if(i < nums.size() && nums[i] <= mark) {
                mark += nums[i++];
            }
            // 否则需要加入新的数字，即加入x，res加一
            else {
                mark += mark;
                ++res;
            }
        }
        
        return res;
    }
};