Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.
Example:
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]
这道题规定了nums
所有值都在[lower,upper]
区间,使得这道题难度降低许多。
我们只需要将lower + 1
插到nums头部,把upper - 1
插到nums末尾,然后遍历数组就可以了,缺失的区间是num[i]+1 ~ num[i+1]-1
。
class Solution(object):
def findMissingRanges(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: List[str]
"""
nums.insert(0, lower - 1)
nums.append(upper + 1)
res = []
for i in range(len(nums) - 1):
left, right = nums[i], nums[i + 1]
if left < right - 1: # 确保right和left之间差 >=2 ,这样才有可能插入区间
if right - left == 2:
res.append(str(right - 1))
else:
res.append(str(left + 1) + "->" + str(right - 1))
return res