Pythonを使用して、指定された合計条件を満たすサブシーケンスの数を見つけるプログラム

numsという配列と別の値kがあるとします。 numsの空でないサブシーケンスの数を見つけて、その最小要素と最大要素の合計がk以下になるようにする必要があります。回答は非常に大きい可能性があるため、回答mod 10 ^ 9+7を返します。

したがって、入力がnums =[4,6,7,8] k =11のような場合、

• [4]、ここでは最小値は4、最大値は4なので、4 + 4 <=11

• [4,6]、ここでは最小値は4、最大値は6なので、4 + 6 <=11

• [4,6,7]、ここでは最小は4、最大は7なので、4 + 7 <=11

• [4,7]、ここでは最小は4、最大は7なので、4 + 7 <=11

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

• リスト番号を並べ替える

• m：=10 ^ 9 + 7

• 左：=0

• 右：=numsのサイズ-1

• res：=0

• 左<=右、実行

  • nums [left] + nums [right]> kの場合、

    • 右：=右-1

  • それ以外の場合

    • num_inside：=右-左

    • res：=（res +（2 ^ num_inside）mod m）mod m

    • 左：=左+ 1

• 解像度を返す

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

例

def solve(nums, k):
   nums.sort()
   m = 10**9 + 7
   left = 0
   right = len(nums) - 1
   res = 0
   while(left <= right):
      if nums[left] + nums[right] > k:
         right -= 1
      else:
         num_inside = right - left
         res = (res + pow(2, num_inside, m)) % m
         left += 1
   return res
nums = [4,6,7,8]
k = 11
print(solve(nums, k))

入力

[4,6,7,8], 11

出力

4