长度为K的数组中长度>1的子数组数量公式(K*(K-1))/2推导疑问

核心前提 #

我们讨论的是连续子数组（数组中一段连续的元素序列），目标是统计其中长度≥2的子数组总数。

方法1：等差数列求和推导 #

假设数组长度为K，我们按子数组的长度分类统计：

• 长度为2的子数组：共有 $K-1$ 个（比如K=3时，对应[0,1]、[1,2]）
• 长度为3的子数组：共有 $K-2$ 个（K=3时，对应[0,1,2]）
• ...
• 长度为K的子数组：共有 $1$ 个

把所有长度≥2的子数组数量相加，得到总和：
$$(K-1) + (K-2) + ... + 2 + 1$$

这是一个首项为1、末项为$K-1$、项数为$K-1$的等差数列，根据等差数列求和公式：
$$\text{总和} = \frac{(\text{首项} + \text{末项}) \times \text{项数}}{2} = \frac{(1 + K-1) \times (K-1)}{2} = \frac{K*(K-1)}{2}$$

方法2：组合数视角推导 #

每个长度≥2的连续子数组，都可以唯一对应一对起始下标i和结束下标j（其中 $i < j$）。

从K个下标中选2个不同的下标（顺序固定，i<j），对应的组合数为：
$$C(K,2) = \frac{K!}{2!(K-2)!} = \frac{K*(K-1)}{2}$$

这和第一种方法的结果完全一致。

结合你的例子验证 #

输入数组{1,2,3}（K=3），代入公式得：
$$\frac{3*(3-1)}{2} = 3$$
对应符合条件的子数组：[1,2]、[2,3]、[1,2,3]，正好3个，和题目输出一致。

内容的提问来源于stack exchange，提问作者Learner