如何计算3长度k < n数组中长度(或一般长度)的不同子序列的数量n？
注意:如果两个子序列中的元素顺序不同,则认为它们是不同的.
例如:假设数组A = [1, 2, 1, 1],那么答案应该是3因为长度只有三个不同的子序列,3如下所示:
[1, 1, 1]
[1, 2, 1]
[2, 1, 1]
数组的大小,数组n <= 10^5中的每个元素A_i <= n.
我的方法:
我想到了蛮力方法,即采用长度元组3并将其插入地图中.但这不是空间/时间效率.
编辑:这是一个采访问题,它说,对于k = 3,预期的时间和空间复杂度是O(n).