arrays - 计算数组中不包括某些特定对的子数组的适当数量？

Question

假设我有一个像这样的数组:

1 2 3 4 5 

给定的对是(2,3)，那么其中不存在(2,3)的可能子数组的数量将是，，

1. 1
2. 2
3. 3
4. 4
5. 5
6. 1 2
7. 3 4
8. 4 5
9. 3 4 5

所以，答案是9。

显然，这样的对还可以有更多。

现在，我想到的一种方法是 O(n^2)，其中涉及查找最大长度 n 的所有此类元素。我可以做得更好吗？谢谢!

Answer 1

让我们看看，这个临时伪代码应该是 O(n):

array = [1 2 3 4 5]
pair = [2 3]
length = array.length
n = 0
start = 0

while (start < length)
{
    # Find next pair

    pair_pos = start
    while (pair_pos < length) and (array[pair_pos,pair_pos+1] != pair)   # (**1)
    {
        pair_pos++
    }

    # Count subarrays

    n += calc_number_of_subarrays(pair_pos-start)  # (**2)

    # Continue after the pair

    start = pair_pos+2
}

print n

注意**1:这似乎涉及到外循环内部的循环。由于数组的每个元素都被访问一次，因此两个循环的复杂度为 O(n)。事实上，重构它以仅使用一个 while 循环可能很容易。

注意 **2:给定一个长度为 l 的数组，有 l+(l-1)+(l-2)+...+1 个子数组(包括数组本身)。计算起来很容易，时间复杂度为 O(1)，不涉及循环。 c/f 欧拉。 :)