给定一个由数字和字符组成的数组，找出两者数目相等的最长连续子数组

Question

假设给定了一个数组，您必须找到包含相同数量字符和数字的最长连续子数组。例如，我们有一个像 ('a',0,'v',2,4,7,'e','f','b',2,5,2,1) 这样的字符数组。

在这种情况下，最长的子数组将是 ('v',2,4,7,'e','f','b',2)，因为它将是 4 个字符和 4 个数字。

我已经解决了类似的问题，比如“最大连续子阵列问题”，但我就是无法解决这个问题。此外，如果这是一个众所周知的问题，那么最好的解决方案是什么？是否可以用 O(n) 的时间复杂度来解决它？

Answer 1

如果范围 [x,y] 具有与字符相同数量的整数，则范围 [0,x] 和 [0,y] 具有相同的 (num ints) - (num chars) 值。我们可以使用它来计算线性时间、线性空间中的答案，方法是维护整数与字符的累积差异的散列。

1. 维护一个最初为空的哈希，它将计数的增量映射到一个索引。（#ints - #chars）。例如，7->22 表示在索引 22 处首次看到 delta 为 7。
2. 跟踪longest_length（最初为 0）和start_index（最初为 nil）
3. 解析数组，跟踪整数和字符的计数。
4. 计算差异。检查你的哈希。如果它存在于散列中，请将索引的差异与您的差异进行比较longest_length并适当更新。如果没有，请更新哈希。

最后，答案是[start_index, start_index + longest_length]。