Pythonで素敵なサブアレイの数を数えるプログラム

numsという配列と別の値kがあるとします。素敵なサブ配列の数を見つける必要があります。サブアレイに奇数がk個ある場合、そのサブアレイは優れたサブアレイであると言われます。

したがって、入力がnums =[1,1,2,1,1]、k =3の場合、2つのサブ配列[1,1,2,1]と[1,2]があるため、出力は2になります。 、1,1]。

これを解決するには、次の手順に従います-

• odd_i：=新しいリスト

• 0からnums-1のサイズのiの場合、実行します

  • nums [i] mod 2が1と同じ場合、

    • odd_iの最後にiを挿入します

• 開始：=0、終了：=k-1

• i：=0

• カウント：=0

• を終了します

  • endがodd_i-1のサイズと同じである場合、

    • j：=numsのサイズ-1

  • それ以外の場合

    • j：=odd_i [end + 1]-1

  • count：=count +（odd_i [start] --i + 1）*（j --odd_i [end] + 1）

  • i：=odd_i [start] + 1

  • start：=start + 1

  • end：=end + 1

• 返品数

例

理解を深めるために、次の実装を見てみましょう-

def solve(nums, k):
   odd_i = []
   for i in range(len(nums)):
      if nums[i] % 2 == 1:
         odd_i.append(i)
   start = 0
   end = k - 1
   i = 0
   count = 0
   while end < len(odd_i):
      if end == len(odd_i) - 1:
         j = len(nums) - 1
      else:
         j = odd_i[end + 1] - 1
      count = count + (odd_i[start] - i + 1) * (j - odd_i[end] + 1)
      i = odd_i[start] + 1
      start = start + 1
      end = end + 1
   return count

nums = [1,1,2,1,1]
k = 3
print(solve(nums, k))

入力

[1,2,3,4,5,6,7,8]

出力

2