Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges. eg: [0,99] : {5, 9,11} => {0~4, 6~8, 10, 12~99}.

idea

• 本来题目给的例子很简单, 就是用2 pointers: prev, curr. 每次比较curr-prev是否大于1, 若大于, 说明有个range了. 最简单的就是5,9, 这个range就是prev+1~curr-1, 如果这个range只有一个数, 那么直接prev+1. 但是如果lower到A[0]之间也有range, 或者A[last]到upper之间有missing range怎么处理, 我一开始加了对应的if/else来处理这2中corner cases. 但觉得还是有点复杂.

Ethan Li的牛答案: 加入虚拟的头和尾

• 正如平时的linkedlist的dummy node, 或者是graph里面的dummy root(记得之前见过从graph的2头夹迫). 这里大牛也是.
• 加入lower-1, 和upper+1. 以及invariant: prev, curr分别指向上一个range的结尾和当前遍历的数字.
• 如图一目了然: .
• 代码实现的漂亮.