1 public class Solution { 2     public int minPatches(int[] nums, int n) { 3         long missed = 1; 4         int index = 0; 5         int result = 0; 6         while (missed <= n) { 7             if (index < nums.length && nums[index] <= missed) { 8                 missed += nums[index++]; 9             } else {10                 missed += missed;11                 result++;12             }13         }14         return result;15     }16 }

这个代码简单但逻辑深刻。它的工作原理如下:

1. 从[1, n]这个范围开始寻找。当你找到一个数在数组中小于当前missed时，将这个数加到missed上，并且将这个数从数组中移除。这样就能形成一个新的范围[1, missed + nums[i]]。

2. 如果没有找到符合条件的数，那么最好的选择是将missed自身加到missed上。因为在之前的步骤中，我们已经能够形成一个[1, missed)的范围。为什么不能直接加一个更大的数呢？

举个例子来理解这个逻辑。如果你有一个范围[1, missed)，再加一个数x。你的目标是形成一个新的范围[1, missed + x)。在这种情况下，missed是最大的缺失数。当前的数无法覆盖到这个missed本身，因此只能选择将missed加到自身。

转载自:https://www.cnblogs.com/shuashuashua/p/5633442.html