分析 miss记录当前集合已经完成[0, miss)所有组合。 当前值nums[i]小于等于miss时，表示在集合中增加nums[i]可以使组合范围增大到[0, miss+nums[i])。 当前值nums[i]大于miss时，增加nums[i]并不能让集合覆盖[0, miss+nums[i])，此时最好的方法是加miss，使得范围增大到[0, 2 * miss)。 class Solution { public: int minPatches(vector<int>& nums, int n) { long miss = 1; int ret = 0, i = 0; while (miss <= n) { if (i < nums.size() && nums[i] <= miss) { miss += nums[i++]; } else { miss <<= 1; ++ret; } } return ret; } };
