在力扣上刷到的一个题，感觉挺有意思，当时起手写了一个近似O(kn?)时间复杂的代码，但提交上去发现果然超时。最后借鉴了另一个题“最小覆盖子串”的思路，在原来的代码上进行了修改，将时间复杂度优化为O(n)。

思路

大致思路是：先将所有的k个数组合并，为了知道每个数字来自哪个数组，给每个数（i）配一个标识（j），表示对应的数组编号，可以用元组列表实现，将该元组列表按i进行升序排序，这样问题变成了类似的“最小覆盖”问题，我们的目的就是要找到两个数i1和i2，使得他们之间的数包含了所有的标识(j)0~k-1，并且i2-i1要最小；

采用“滑动窗口”法，建立一个哈希表存储当前窗口中包含的标识0~k-1的个数，从最左边开始，右边界每次往移右一格，并把它对应的j的个数在哈希表中+1，知道当前窗口包含了0~k-1中的每个数至少一次，此时开始移动左边界，左边界每次往右移一格，并且检查区间是否更小，如果更小，更新区间和区间长度，知道当前窗口中没有再包含0~k-1。

关键点

1、如果在检查窗口中是否包含0~k-1时采用遍历法，那么每次都需要花费额外的O(k)的时间，但其实我们只需要维护一个变量来表示当前窗口中包含的0~k-1的个数即可，这样每次检查都能在O(1)的时间内完成

2、在排序过程中，可以直接用自带的排序方法进行排序，事实证明也能通过，但其实由于原来的k个数组是已经排好序的，所以，我们可以用“分组排序”的思想，直接进行比较后一一放入，这样排序过程也能在O(n)的时间内完成

3、在维护“检查变量”时，我们只关注哈希表中的个数是否大于等于1，所以我们只在当某个标识超过0或者<1时改变该变量

源代码

Python版本：

import sysclass Solution:def __sort(self, nums):  # 可以自己手动排序passdef smallestRange(self, nums: List[List[int]]) -> List[int]:min_length = sys.maxsize  # 最小区间长度fragment_range = [0, 0]  # 最小区间n = len(nums)num_tuple = [(i, j) for j in range(n) for i in nums[j]]  # 元组列表[数字,数组编号]num_tuple.sort(key=lambda x:x[0])  # 排序num_dict = {i:0 for i in range(n)}  # 保存每个标识的个数distance = 0  # 包含0~k-1中的个数left = 0right = 0while right < len(num_tuple):num_dict[num_tuple[right][1]] += 1if num_dict[num_tuple[right][1]] == 1:distance += 1while distance == n:  # 满足条件if num_tuple[right][0] - num_tuple[left][0] < min_length:  # 更新fragment_range[0] = num_tuple[left][0]fragment_range[1] = num_tuple[right][0]min_length = num_tuple[right][0] - num_tuple[left][0]num_dict[num_tuple[left][1]] -= 1if num_dict[num_tuple[left][1]] < 1:distance -= 1left += 1right += 1return fragment_range

空间开销有点大，部分变量可以合并或者去掉，比如区段右边界其实可以从左边界和区间长度算出来。