题目地址：
https://leetcode.com/problems/missing-ranges/
给定一个无重复数字的长
n
n
n
升序数组
A
A
A
，再给定一个区间
[
l
,
u
]
[l,u]
[
l
,
u
]
，题目保证
l
≤
A
[
0
]
,
A
[
n
−
1
]
≤
r
l\le A[0], A[n-1]\le r
l
≤
A
[
0
]
,
A
[
n
−
1
]
≤
r
。求所有
[
l
,
r
]
−
A
[l,r]-A
[
l
,
r
]
−
A
所剩的区间族。如果区间是单元集则就是它一个数，否则写成
"a->b"
的形式。
代码如下：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> res = new ArrayList<>();
int start = lower;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == start) {
start = nums[i] + 1;
continue;
}
if (nums[i] == start + 1) {
res.add(String.valueOf(start));
} else if (nums[i] > start + 1) {
res.add(start + "->" + (nums[i] - 1));
}
start = nums[i] + 1;
}
if (start == upper) {
res.add(String.valueOf(start));
} else {
res.add(start + "->" + upper);
}
return res;
}
}
时间复杂度
O
(
n
)
O(n)
O
(
n
)
，空间
O
(
1
)
O(1)
O
(
1
)
。