Patching Array
给一个已排序数组和一个n, 问这个数组添加几个元素能让其中的任何个数数字之和等于n. 这个题需要找规律. 规律是数组从小往大求和. 这个和就是能覆盖的数组, 当遇到一个数字无法覆盖的时候, patch应该是当前可覆盖范围最大值+1, 因为这样才能保证每个数都覆盖, 然后继续求和, 直到n.
public class Solution {
public int minPatches(int[] nums, int n) {
int count = 0;
int i = 0;
long sum = 0;
while(sum < n) {
if(i < nums.length && nums[i] <= sum+1)
sum+=nums[i++];
else{
sum+=sum+1;
count++;
}
}
return count;
}
}