哈希

题目分析 如果称一个长度$length$「满足条件」，即表示在$nums$中所有长度为$length$的子数组中存在一个唯一的子数组，那么本题要求的，就是最小的满足条件的长度$length$。 基本思路 分析题目可以发现以下两条性质： 如果一个给定的长度$length$无法满足条件，即该长度对应的所有子数组中没有单独出现的，那么所有小于等于它的长度都一定不满足条件，说明要找的最小长度一定是大于$length$的； 相反，如果一个长度$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$的变化如下： $w \rightarrow w\times base$（将每一个元素中$base$的指数都增加1，为新元素腾出位置） $w \rightarrow w-nums[i-length]\times b^{length}$（删除$nums[i-length]$，这里由于上一步将$base$的指数加了1，此处对应的指数就变成了$length$而非原先的$length-1$） $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