LeetCode 题解工作台
汇总区间
给定一个 无重复元素 的 有序 整数数组 nums 。 区间 [a,b] 是从 a 到 b （包含）的所有整数的集合。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说， nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。 列…
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们可以用双指针 和 找出每个区间的左右端点。 遍历数组，当 $j + 1 < n$ 且 $nums[j + 1] = nums[j] + 1$ 时，指针 向右移动，否则区间 $[i, j]$ 已经找到，将其加入答案，然后将指针 移动到 $j + 1$ 的位置，继续寻找下一个区间。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给定一个 无重复元素 的 有序 整数数组 nums 。
区间 [a,b] 是从 a 到 b（包含）的所有整数的集合。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b"，如果a != b"a"，如果a == b
示例 1：
输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"] 解释：区间范围是： [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"
示例 2：
输入：nums = [0,2,3,4,6,8,9] 输出：["0","2->4","6","8->9"] 解释：区间范围是： [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9"
提示：
0 <= nums.length <= 20-231 <= nums[i] <= 231 - 1nums中的所有值都 互不相同nums按升序排列
解题思路
方法一：双指针
我们可以用双指针 和 找出每个区间的左右端点。
遍历数组，当 且 时，指针 向右移动，否则区间 已经找到，将其加入答案，然后将指针 移动到 的位置，继续寻找下一个区间。
时间复杂度 ，其中 为数组长度。空间复杂度 。
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
def f(i: int, j: int) -> str:
return str(nums[i]) if i == j else f'{nums[i]}->{nums[j]}'
i = 0
n = len(nums)
ans = []
while i < n:
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ans.append(f(i, j))
i = j + 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks the candidate's ability to optimize array traversal.
- question_mark
Evaluates how the candidate handles edge cases in a sorted array.
- question_mark
Assesses the candidate's approach to time and space complexity trade-offs.
常见陷阱
外企场景- error
Failing to handle single-element ranges correctly.
- error
Not optimizing the solution when scaling the array size.
- error
Misinterpreting the problem as needing a brute-force solution instead of an efficient array-driven approach.
进阶变体
外企场景- arrow_right_alt
Allow duplicates in the array and handle them.
- arrow_right_alt
Modify the problem to deal with unsorted input arrays.
- arrow_right_alt
Implement the problem with additional constraints like a maximum range size.