子数组和子序列,特别是在一个区间内,或者一个窗口内的子数组个数或者子序列个数问题是非常常见的一类题目,与其他算法结合在一起,求子数组或者子序列数量是非常常见的题目,今天就来总结 一下。
如何统计区间内子数组数量
如何统计区间内子序列数量
子序列是子数组的特殊形式,它不要求保留在原数组中的顺序。一个长度为k的区间内所有子序列的个数就是一个幂集,每个元素都有「选」和「不选」,因此这个区间所有子序列个数是2k个。
典型题目
题目 | 题解 | 说明 |
---|---|---|
1498. 满足条件的子序列数目 | 题解 | |
题解 | ||
题解 | ||
题解 |