将包含特定索引'i'的子数组的个数是多少？

Question

考虑一个'n'个元素的数组，其中a i是索引i的元素，其中1 <= i <= N。我需要计算将包括特定索引i的子数组（数组的连续子序列）的数量。例如，考虑A = [1,2,3,4,5]索引2处的元素2将包含在8个子数组中-{2}，{1,2}，{2,3}，{1,2,3}，{2,3,4 }，{1,2,3,4}，{2,3,4,5}，{1,2,3,4,5}。

是否有一种方法可以根据数组大小n和选定的索引i来构造此公式？

Answer 1

的子数组（数组的连续子序列）的数量

包括索引i的序列数将等于i左侧的序列数乘以右侧的数。对于左侧和右侧，我们都必须包括空序列。

在您的示例中为：

left: {}, {1}
right: {}, {3}, {3,4}, {3,4,5}

将每个左序列与每个右序列配对，其中i显然在中心，在您的示例中为您提供了8个子阵列。 （如果您认为上方和下方是集合，那么您正在寻求形成Cartesian Product）。

[左序列数仅为i，在右边数为n-i+1。因此，总数为i*(n-i+1)。