查找不包括某些对的连续子数组的数量

Question

一个数组有多少个连续的子数组不包含数组的某些位置对？例如。如果数组 ={11,22,33,45} 并且如果我们不想包含位置编号 (1,3) 和 (2,4) 则存在的连续子数组的数量为 7，如下所示 {{11 },{22},{33},{44},{11,22},{22,33},{33,45}}.

我解决问题的尝试：

如果存在两对使得 {...,a1, ...,a2 ,..,b1, ..,b2} 其中 n 是元素的数量，并且 (...) 表示存在是这些位置之间的元素。

第一种情况：我们不能包括 {a1,b1} 和 {a2,b2} 那么我们必须计算可能的组合数量，即 n*(n+1)/2 - 否。可能的组合包括 {a2,b1} 涵盖了所有可能的

情况 2。如果我们不能包含对 {a1,b2} 和 {a2,b1}，那么我们只需减去包含 {a2,b1} 的可能性的数量，这涵盖了所有可能的情况。

第三种情况：如果我们不能包含对 {a1,a2} 和 {b1,b2} 那么我们必须单独减去包含这些位置的可能子数组

我面临的问题是我无法推导出公式并将这些案例扩展到超过 2 对以计算可能的解决方案的数量，即使在制定案例之后也是如此。所以，我需要这方面的帮助。

来源：这是问我朋友的一个面试问题，他无法回答。

Answer 1

好的，让我们再看看数组{11,22,33,44}。

假设您要查找所有以 11（索引=1）开头的子数组。现在你只需要查看限制 (a,b) 其中 index<=a 和 b 是最小的，因为如果你有例如(2,3) 这自动意味着 (1,4) 或 (2,4)。

要找到最小的 b，请使用以下代码（我使用 C#）：

public static int  findRestrictingIndex(int currentIndex, List<Tuple<int, int>> restrictions)
    {
        int result = int.MaxValue;
        foreach (var pair in restrictions)
        {
            if (currentIndex <= pair.Item1)
            {
                if (pair.Item2 < result)
                    result = pair.Item2;
            }
        }
        return result;
    }

如果您运行此代码，您将收到 3（来自 (1,3)）。以 11 开头的数组的数量是 3-1=2，因为您可以将数字与 11 相加，直到排除索引 3。

对每个索引执行此操作即可完成：

int arrayLength = 4;

//excluded positions, zero-based
List<Tuple<int, int>> restrictions = new List<Tuple<int, int>>();
restrictions.Add(new Tuple<int, int>(0, 2));
restrictions.Add(new Tuple<int, int>(1, 3));
restrictions.Add(new Tuple<int, int>(4, 4));    //dummy element when there is no restriction

int numOfSubarrays = 0;
for (int currentIndex = 0; currentIndex < arrayLength; currentIndex++)
{
    numOfSubarrays += findRestrictingIndex(currentIndex, restrictions) - currentIndex;
}
Console.WriteLine(numOfSubarrays);

查找不包括某些对的连续子数组的数量

Finding number of contiguous subarrays not including certain pairs

algorithm

math

combinations

combinatorics