最近寫到的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 就可以 抱歉耍蠢了