狗家月初昂塞

楼主有狗家的面经总结吗？多谢

Teddies 发表于 2018-12-7 23:41
首先补充一下这道题不用考虑空集，不过其实考不考虑就是答案加一的事，不影响做题。

在没有重复的时候 ...

感谢楼主分享。follow up我想可以这样：
例：[1 1 1 2 2 2 2 3 3] K = 4
把所有的unique数字和它们出现的次数提取出来：
unique数字：a = [1 2 3]
出现次数：   t = [3 4 2]

然后还按左右指针的办法，左指针i=0，右指针j=2。a[ 0 ]+ a [ 2 ] = 1 + 3 <=4。此时a[0..2]范围内的每一个数字a[k]都可以在subgroup在出现0, 1, ... 或t[k]次，即有(t[k]+1)种可能。不过a[0]必须要出现至少一次，所以有t[0]种可能。不同数字的出现次数是互不相关的，因此[0..2]这个范围内总共有(t[ 0 ] ) * (t[ 1 ] + 1) * (t[ 2 ] + 1) = 3 * 5 * 3 = 45种可能的subgroup的选择方法。接下来的指针移动方法和无重复数字的情况相同。

没有重复数字时，t其实就是[1 1 1]，所以[0..2]范围内就只有1 * (1+1)*(1+1) = 2^2 = 4种情况，这是上述一般方法的一个特例。