arrays - 查找最多具有 k 个奇数元素的不同连续子数组的数量

Question

给定一个整数数组 nums，找到最多具有 k 个奇数元素的不同连续子数组的数量。当两个子数组至少有一个不同的元素时，它们是不同的。

我能够在 O(n^2) 的时间内完成。但需要 O(nlogn) 的解决方案。

示例 1:

Input: nums = [3, 2, 3, 4], k = 1
Output: 7 
Explanation: [3], [2], [4], [3, 2], [2, 3], [3, 4], [2, 3, 4]
Note we did not count [3, 2, 3] since it has more than k odd elements.

示例 2:

Input: nums = [1, 3, 9, 5], k = 2
Output: 7
Explanation: [1], [3], [9], [5], [1, 3], [3, 9], [9, 5]

示例 3:

Input: nums = [3, 2, 3, 2], k = 1
Output: 5
Explanation: [3], [2], [3, 2], [2, 3], [2, 3, 2]
[3], [2], [3, 2] - duplicates
[3, 2, 3], [3, 2, 3, 2] - more than k odd elements

示例 4:

Input: nums = [2, 2, 5, 6, 9, 2, 11, 9, 2, 11, 12], k = 1
Output: 18

Answer 1

我们可以通过两步过程在次二次复杂度中解决这个问题。首先用两个指针勾勒出相关的窗口，我们将用它来构建广义后缀树。我们可以通过注意每个重叠仅插入两次来证明所有窗口的总长度为 O(n)。第一个窗口是通过从第一个元素向右扩展到我们可以保留有效子数组的最远距离来构造的。随后的窗口通过以下方式创建:(1) 在下一个奇数元素之后扩展左指针，以及 (2) 将右指针扩展到我们可以保留有效子数组的程度。

Example 1:

3, 2, 3, 2
k = 1

windows: [3 2], [2 3 2]


Example 2:

1, 2, 2, 2, 3, 4, 4, 5, 5
k = 2

windows:
[1 2 2 2 3 4 4], [2 2 2 3 4 4 5], [4 4 5 5] 

构建广义后缀树。不同子集的计数将等于存储在树中的后缀的累积长度之和。 (我的意思是“累积长度”:例如，给定后缀“abc”，我们将添加 1 + 2 + 3，每次从后缀的开头延伸得更远。或者通过公式 n * (n + 1)/2 )

如 kcsquared 所述 in the comments ，不需要广义后缀树。相反，我们可以使用一种已知的方法来“计算具有后缀数组和最长公共(public)前缀数组的不同子串总数，而不是对 n - suffix_array_elements 求和，...用该索引的最大右边界替换 n。”