two pointers
双指针
Missing Ranges
Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].
思路
我们用一个指针 prev 记录上次 range 的结尾,一个指针 curr 记录当前遍历到的数字,如果 curr 和 prev 相差大于 1,说明一个 missing range,我们将其加入结果列表中就行了。这题主要是有几个 corner case 要解决:
- 如何处理 lower 到第一个数,和最后一个数到 upper 的 missing range?
- 如何区分 range 中只有一个数和多个数?
- 如何有效的得到 missing range 的起始和结束值,同时保证不会包含数组中的数字?
对于第一个问题,我们要做的就是在让 for 循环多判断两次。想象一下假设数组前有一段连续的负无穷到 lower-1,数组后有一段 upper+1 到正无穷,这样是等价与上下界的。本来如果不考虑头尾,那 for 循环本应是从 1 到 length-1 的,但是为了判断头,我们从 0 开始,将下标为 0 的数和 lower-1 比较得到第一个 range。最后循环到 length 停止,当下标为 length 时,我们将当前指针指向 upper+1,并判断 upper+1 和数组末尾是否能构成最后一个区间。
对于第二个问题,我们只要判断这个区间的起止是否一样就行了
对于第三个问题,我们用 prev+1 和 curr-1 来标记这个区间的起止,因为 prev 和 curr 都是数组中的数,所以解决了每个区间的边界问题
|
|