3934. 最短唯一子数组

题目分析

如果称一个长度$length$「满足条件」，即表示在$nums$中所有长度为$length$的子数组中存在一个唯一的子数组，那么本题要求的，就是最小的满足条件的长度$length$。

基本思路

分析题目可以发现以下两条性质：

  1. 如果一个给定的长度$length$无法满足条件，即该长度对应的所有子数组中没有单独出现的，那么所有小于等于它的长度都一定不满足条件，说明要找的最小长度一定是大于$length$的；
  2. 相反，如果一个长度$length$可以满足条件，即存在一个单独出现的长度为$length$的子数组，那么在该长度之下可能还有能够满足条件的长度，结合本题要求最小长度，因此要找的长度一定是小于等于$length$的。

可以发现，只要确定一个长度是否满足条件，即可确定需要的答案究竟大于还是小于这个长度，因此可以想到采用二分查找的方式寻找答案。

思路1：列表模拟计算

根据上述分析可以发现，二分查找的判断函数应判断给出的中间值$mid$是否是一个满足条件的长度，因此最暴力的方式就是：直接用列表模拟找所有长度为$mid$的子数组，并逐个转为tuple类型用哈希表计数（转为tuple是因为list类型无法直接在哈希表里当作键来计数），其中列表维护长度为$mid$的子数组，即可采用滑动窗口的方式维护。代码很简单直观，如下：

def check(mid):
	cur = []
	tot = defaultdict(int)
	for i in range(n):
		cur.append(nums[i])
		if i < mid-1:
			continue
		tp = tuple(cur)
		tot[tp] += 1
		cur.pop(0)
	return 1 in tot.values()

不过上面代码中，list转tuple以及pop操作的空间复杂度都很高，最坏情况下单单$tot$中存储值的数量都会逼近$O(n^2)$，因此最终上述代码超内存。

思路2：列表哈希化处理

既然用列表计数会超内存，那么就需要想将列表压缩的方法。可以发现，如果将列表压缩成一个数字，那么空间复杂度将大大降低，因此这里可以借鉴哈希化的方法。

什么叫哈希化？如果要将一个列表哈希化，即意味着用一个特定数字表示该列表。如果要用一个数字$w$代替一个长度为$length$的列表$lst$，则可以使用一个质数$base$，令：

$$w = lst[0]\times base^{length-1}+lst[1]\times base^{length-2}+...+lst[length-1]\times base^0$$

即可使用数字$w$表示列表$lst$。

因此可以定义$w$，表示当前长度为$length$的子数组对应的数字，如果依旧用上述滑动窗口的方式对其增减元素，假设当前要增加的元素是$nums[i]$，那么要删除的元素就是$nums[i-length]$，即可知道$w$的变化如下：

  1. $w \rightarrow w\times base$（将每一个元素中$base$的指数都增加1，为新元素腾出位置）
  2. $w \rightarrow w-nums[i-length]\times b^{length}$（删除$nums[i-length]$，这里由于上一步将$base$的指数加了1，此处对应的指数就变成了$length$而非原先的$length-1$）
  3. $w \rightarrow w+nums[i]$（加上$nums[i]$，此处省略$base^0$）

因此根据上述步骤即可实现元素的增减，从而将所有子数组压缩成一个单独的数字。

实现细节

需要注意的是，如果按照上述的计算方式，当$nums$中的值很大并且$length$很大时，$w$的值就会很大，因此可以使用另一个大质数$mod$来对$w$的值不断取模，从而保证不会超出整数范围，同时减少大数相乘的计算量，减少时间。

同时，按照思路2进行计算时，可以先计算出第一个窗口对应的值，这样，在后面进行增减运算的循环中不会在同一个循环中实现太多功能，增强可读性。

在本题中，如果只用一组$base, mod$数对将每一个子数组进行压缩，不会出现哈希值的冲突，但当数据量增大时，为了防止哈希值的冲突，可以再增加一组$base2,mod2$的值对每一个子数组计算出另一个压缩后的数字，两者同时对应一个子数组，即可降低哈希值冲突的可能性。 （在下面的代码中，我给出了用两组值分别压缩子数组的方式，如果追求运行速度，可以将有关$b2,m2,pow2,w2$的计算全部删除，可以降低运行时间）

复杂度

时间复杂度：$O(n\cdot logn)$ 空间复杂度：$O(n)$

代码

class Solution:
    def smallestUniqueSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        b1, m1 = 1_000_07, 1_000_000_007 # 第一组数据
        b2, m2 = 1_000_09, 1_000_000_009 # 第二组数据
        def check(mid):
            pow1 = pow(b1, mid, m1)
            pow2 = pow(b2, mid, m2)

            w1, w2 = 0, 0
            for i in range(mid):
                w1 = (w1*b1+nums[i])%m1
                w2 = (w2*b2+nums[i])%m2 # 用第二组数据进行压缩

            cnt = defaultdict(int)
            cnt[(w1, w2)] = 1
            for i in range(mid, n):
                w1 = (w1*b1+nums[i]-nums[i-mid]*pow1)%m1
                w2 = (w2*b2+nums[i]-nums[i-mid]*pow2)%m2 # 用第二组数据进行压缩
                cnt[(w1, w2)] += 1

            for v in cnt.values():
                if v == 1:
                    return True
            return False

        l, r = 1, n
        while l<=r:
            mid = (l+r)//2
            if check(mid):
                r = mid-1
            else:
                l = mid+1
        return l