包含特定索引 'i' 的子数组的数量是多少?

What is the count of subarrays that will include a particular index 'i'?

考虑一个包含 'n' 个元素的数组,其中 ai 是索引 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 构建公式?

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

在您的示例中,这些将是:

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

将每个左序列与每个右序列配对,i 显然位于中心,在您的示例中给出 8 个子数组。 (如果您将上面的左和右视为集合,那么您正在寻求形成 Cartesian Product)。

左边的序列数刚好i,右边的序列数n-i+1。因此总数为 i*(n-i+1).