如何搜索 0 数组中的所有区间小号，1 s 和 2包含相同数量的 1 的 s s 和 2是吗？
例子:
[0,1,1,2,2]
将返回 3 个间隔
[0,1,1,2,2] [1,1,2,2] [1,2]
我不想暴力破解它。是否有任何非常简单的算法可用于此类情况？我需要一些灵活的东西。
最佳答案
首先，为了算法的清晰度，我将把数字更改为字母:Z、A、B。输入现在可以表示为一个简单的字符串:“ZAABB”。同样为了清楚起见，我将在每个位置插入一个句点作为间距:“.Z.A.A.B.B.”。
这是一个符号平衡问题，很容易处理。遍历数组，跟踪每个位置的多余部分。 Z 不会改变计数； A 递增； B 递减。这给了我们
"00011221100".
现在，提取交替计数，每个“间隔”处的计数，句点:
".Z.A.A.B.B."
"0 0 1 2 1 0"
从这里，很容易找到匹配的计数。 每一对 匹配计数都会为您提供具有相同数量的 A 和 B 的子字符串的索引。你有三对 0 匹配和一对 1 匹配，产生子串
"0 0 1 2 1 0"Z
"0 0 1 2 1 0"Z A A B B
“0 0 1 2 1 0” A A B B
"0 0 1 2 1 0"A B
是否足够清晰，您可以实现？
关于algorithm - 搜索满足特定条件的所有区间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54137679/