题目要求
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.
Example 1:
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, 6, which now covers the range [1, 6].
So we only need 1 patch.
Example 2:
Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].
Example 3:
Input: nums = [1,2,2], n = 5
Output: 0
假设有一个有序的正整数数组 nums 和一个整数 n，最少添加几个元素到这个数组中，使得从 1 - n 的所有整数都可以由这个数组中的值的或是几个值的和构成。
思路和代码
这里的核心思路在于如何找到一个规律，使得我们可以在前一个规律的基础上添加一个数达到下一个范围。假设当前的数组可以组成从 [1…k] 的所有整数，那么我们下一步如果往数组中添加 x，则数组就可以组成从 [1…k+x] 的所有整数。因此，为了只打最少的补丁，我们会希望每一次往数组中添加的元素所能够到达的范围越远越好，因此我们会 patch 一个 k + 1 上去从而使得数组最远扩展到 [1…2k+1]。如果当前数组中存在一个数组 m 位于[k+1, 2k+1] 这个范围中，则我们的数组可以再次扩展到[1…2k+m+1]。
public int minPatches(int[] nums, int n) {
int count = 0;
long max = 0;
int index = 0;
while(max < n) {
if(index<nums.length && max + 1 >= nums[index]) {
max += nums[index++];
} else {
count++;
max += max + 1;
}
}
return count;
}
这里需要注意的细节是数组的溢出。这里用 long 型避免数组值的溢出。