Sub Array and Seb Sequences Made Easy

子数组和子序列，特别是在一个区间内，或者一个窗口内的子数组个数或者子序列个数问题是非常常见的一类题目，与其他算法结合在一起，求子数组或者子序列数量是非常常见的题目，今天就来总结一下。

如何统计区间内子数组数量

子数组的数量只与区间长度有关系，对于一个区间长度为n的数组，其非空子数组数量为n * (n+1)/2。

具体计算过程，可以用子数组长度来递推：

1). 长度为1，这时子数组数量为n个 2). 长度为2时，这时子数组数量为n - 1个 3). 长度为n - 1时，这时子数组数量为2 4). 长度为n时，这时子数组数量只有一个1，为1

可以发现，这是一个等差数列，求和之后就是n*(n+1)/2。

子序列是子数组的特殊形式，它不要求保留在原数组中的顺序。一个长度为k的区间内所有子序列的个数就是一个幂集，每个元素都有「选」和「不选」，因此这个区间所有子序列个数是2^k个，包括空子序列，如果要求非空，那就再减去一个1。

具体计算过程，需要用到组合数学：

1). 一个都不选C(n, 0) = 1 2). 一个一个的选，C(n, 1) = n 2). 两个选，C(n,2) 3). n - 1个，C(n, n - 1) 4). n个，C(n, n) = 1

求和就是2ⁿ，如果非空就是2ⁿ - 1。