Pythonで合計がkの倍数となる長さ2以上の部分リストを検出する方法

非負の整数からなるリスト nums と、正の整数 k が与えられたとします。このとき、要素の合計が k の倍数になる「長さ 2 以上の部分リスト（サブリスト）」が存在するかどうかを判定します。

たとえば、入力が nums = [12, 6, 3, 4]、k = 5 の場合、出力は True になります。これは、部分リスト [12, 3] を選ぶと合計が 15 となり、5 で割り切れるためです。

アルゴリズムの考え方

この問題は、累積和の剰余（mod k）を利用することで効率的に解けます。ポイントとなるのは次の性質です。

「2つの累積和の剰余が等しい場合、その間にある要素の合計は必ず k の倍数になる」

そこで、各インデックスにおける累積和を k で割った余りをハッシュマップに記録していき、同じ余りが再び現れたときに、そのインデックスの差が 2 以上であれば、条件を満たす部分リストが存在すると判断できます。

手順

• sum = 0 と初期化する
• 空のマップ m を作成し、m[0] = -1 を設定する（リスト開始前の仮想インデックスを表す）
• i を 0 から nums の長さ - 1 まで繰り返す：
  • sum += nums[i]
  • sum %= k
  • sum が m に既に存在する場合：i - m[sum] >= 2 なら True を返す
  • 存在しない場合：m[sum] = i を記録する
• ループが終了しても見つからなければ False を返す

なお、初期値として m[0] = -1 を設定しておくことで、「リストの先頭から始まる部分リスト」も正しく扱えるようになります。

実装例

以下がPythonによる実装です。

class Solution:
   def solve(self, nums, k):
      sum = 0
      m = {}
      m[0] = -1
      for i in range(0, len(nums)):
         sum += nums[i]
         sum %= k
         if sum in m:
            if i - m[sum] >= 2:
               return True
         else:
            m[sum] = i
      return False
ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))

入力

[12, 6, 3, 4], 5

出力

True

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n) です。また、ハッシュマップに保存される剰余は最大でも min(n, k) 種類なので、空間計算量も O(min(n, k)) に抑えられます。すべての部分リストを列挙する総当たり法（O(n²) 以上）と比較して、はるかに効率的なアプローチといえます。