algorithm - 计算子数组中的唯一值

Question

数组 a*b 是给定的，其中包含最多 1e5 的数字，我们必须对每个 k*k 子数组中的唯一数字的计数求和， 有 a-k*b-k 子数组 例如

1 2 3 4 
3 2 4 1

对于 k=2 子数组是

{1,2,3,2}(3distinct values)
{2,3,2,4}(3distinct values)
{3,4,4,1}(3distinct values)

输出为9

有没有比使用存储实际处理的 k*k 子数组中每个数字出现次数的表更快的方法(例如，在索引 3 处，我们将 3 的计数存储在子数组中)，移动k*k 窗口加 1 并从右侧添加值并从左侧移除值，如果增量值是 1 - 递增唯一数字计数器；如果递减后的值为 0 - 递减唯一数字计数器。 到达行尾后，向下走 1 并向相反方向移动。 不担心内存使用，我只是在寻找一种更快地完成此操作的方法

Answer 1

a == b 是一个等价关系。 给定一个元素集(你的子数组)，你可以找到与你找到的方法的关系的等价类:

对于子数组 A 中的每个元素 x，您采用 c[x]，它是一个 int(c 数组元素全部初始化为 0 ).如果这个 c[x] == 0 那么你有一个新的独特元素 c[x]++。否则你增加 c[x]。

此算法与子数组中的元素数量线性(显然，您对每个子数组重复此过程并对结果求和以获得所需结果)。

但是时间复杂度不能再低了，因为无论如何你都需要检查每个元素。