目标
给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有 非空子数组中 不同元素的个数。
换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。
其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。
返回 nums 唯一性数组 的 中位数 。
注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。
示例 1：
输入：nums = [1,2,3]
输出：1
解释：
nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。示例 2：
输入：nums = [3,4,3,4,5]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。示例 3：
输入：nums = [4,3,5,4]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。说明：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路
定义数组的唯一性数组为其所有 子数组 中不同元素个数从小到大排序，求唯一性数组的中位数。
长度为 n 的子数组的个数为 n(n+1)/2，唯一性数组的中位数下标为 n(n+1)/4 - 1 是第 (n(n+1)/2 + 1)/2 个元素。
问题的关键在于，如何快速判断数组中不同元素的个数。我们想要这样一个hash表，可以根据 start end 动态调整其中的元素。
一般来说枚举子数组使用的是双层循环，外层枚举起点，内层从起点开始枚举终点直到结尾，当然也可以外层枚举终点，内层枚举0到终点作为起点，时间复杂度为 O(n^2)。这里的问题在于如何保存区间与对应不重复元素个数的对应关系，以及如何计算不重复元素个数。本来 O(n^2) 就会超时，如果针对每个区间再循环判断，就更不行了。这里其实可以模拟变长的滑动窗口，通过修改窗口中加入与移除元素在map中对应的计数，如果计数为0则删除，这样map里的元素个数即为当前窗口内不重复元素个数。但是并没有保存这个状态（区间对应的不同元素个数）。我们可以将 start, end 压缩到一个long型数字中，倒是也可以记录。假如我们有了这个对应关系，我们还需要将它排序然后取中位数。
看了题解使用的是二分+滑动窗口，确实比较绕，我也没有仔细想清楚，这里面有几个关键点：
- 唯一性数组中元素的取值范围是
1 ~ n，元素递增的步长为1，如果某个子数组比之前的子数组多了2个不同的元素，那么总是可以去掉其中一个使得子数组仅多1个不同元素。 - 思考 唯一性元素的个数 小于等于 m 的子数组有多少个？找到唯一性元素个数第一次覆盖
(n(n+1)/2 + 1)/2的 m 就是要找的答案。 - 假设我们已经知道 m 对应的 cnt，只需要找到第一个大于等于
(n(n+1)/2 + 1)/2的cnt即可，可以使用二分查找。 - 问题转化为 计算唯一性元素的个数 小于等于 m 的子数组个数。使用滑动窗口。
而这里需要计算的是子数组中不同元素的个数，
// todo
代码