搜索满足特定条件的所有区间
Searching for all intervals meeting a specific condition
如何在包含相同数量的 1 和 0、1 和 2 的数组中搜索所有间隔=14=]s?
示例：
[0,1,1,2,2]
会return 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".
现在，提取交替计数，每个 "spacer" 处的计数，句点：
".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
您是否清楚地实施了？
在原始数组中放入 -1 而不是 2。然后，问题将简化为：Zero sum SubArray
如何在包含相同数量的 1 和 0、1 和 2 的数组中搜索所有间隔=14=]s?
示例：
[0,1,1,2,2]
会return 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".
现在，提取交替计数，每个 "spacer" 处的计数，句点：
".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
您是否清楚地实施了？
在原始数组中放入 -1 而不是 2。然后，问题将简化为：Zero sum SubArray