最近写到的OA题目, 可是有testcase超时, 不知道有没有人有啥想法
题目:
有一个array, 你要找出所有不同subarray的数量, 每个sub arrays最多包含k个奇数数字.
范例 1:
array = [1, 2, 3, 4] & k = 1
总个会有[1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [2, 3, 4]这八种, 要return 8
范例 2:
array = [1, 1, 2, 3] & k = 2
会有[1], [1, 1], [1, 1, 2], [1, 2], [2], [2, 3], [3], [1, 2, 3], 要return 8种
p.s
array不是sorted的
array的size在1~n之间
我的解法是暴力解O(n^2),可是有些testcase会超时, 不知道有没有O(n)还是O(nlogn)解法的
更新1:
要求是distinct subarray, 所以范例2 会有两个array [1], [1], 这样算一组
更新2:
范例2有错更新一下

要连续？然后我觉得会被叫去problem solve板

sub array的定义是连续的array感谢 我应该去那个板问的

范例二是回传6吧 1 2 3不算一种解吗?如果是找sybarray数量 范例2的两个1 应该要分开看?用有点变化的前缀和配二分搜应该可以nlogn解出来

[1, 2, 3]也算 抱歉忽略了

应该还有[1 2]跟[3]吧

先把array刷一次然后分成奇数跟偶数然后用排列组合相乘就求出来了应该可以再O(n)解决我没试过 但直觉这样是对的抱歉没看到最多k个奇数 所以应该是O(n+k)

第二个为例，数学模型应该是（x^0+x^1+x^2)(x^0+x^1)(x^0+x^1)的系数和，但因为条件是奇数，所以要先算出一三个括号x次方小于k的系数和，那只需要做一些多项式运算，不知道这样的方法有没有比较快？

如果相同pattern视为一种感觉满困难的 可以请教n平方的方法吗

这个应该都是用back tracking的技巧来写吧

应该可以用two pointer维护区间奇数值 时间O(n)ㄜ 没看到不能重复 当我没说吧

我觉得应该用segment tree可以解吧 keep每个区间的奇数数量 O(nlgn)啊 想了一下应该On 就可以 抱歉耍蠢了