Pythonで配列内にk回以上繰り返される長さmのパターンが存在するかを判定する方法

正の整数からなる配列 nums が与えられたとき、長さ m のパターンが k 回以上繰り返されているかどうかを判定する問題を考えてみましょう。ここでいう「パターン」とは、1つ以上の値からなる連続した(重なり合わない)部分配列であり、複数回繰り返されるものを指します。つまり、配列の中に長さ m の連続する部分列が k 回以上出現しているかを確認する必要があります。

例として、nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1]、m = 3、k = 2 が入力された場合、出力は True になります。これは、パターン [1,4,3] が配列内に3回出現しているためです。

解法のアプローチ

この問題は、Pythonのスライスとリスト比較を組み合わせることで、非常にシンプルに解くことができます。手順は以下の通りです。

• インデックス i を 0 から nums の長さ - 1 まで順に処理します。
• sub1: nums[i] から nums[i + m*k - 1] までの部分配列(長さ m*k)
• sub2: 長さ m の部分配列 nums[i:i+m] を k 回繰り返して作った配列
• sub1 と sub2 が一致すれば、その時点で True を返します。
• すべての i を調べて一致しなければ、False を返します。

ポイントは、長さ m*k の区間が「長さ m のブロックが k 個きれいに並んだもの」と完全に一致するかを確認することです。一致していれば、そのブロックが k 回以上繰り返されていることになります。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def solve(nums, m, k):
    for i in range(len(nums)):
        sub1 = nums[i:i+m*k]
        sub2 = nums[i:i+m]*k
        if sub1 == sub2:
            return True
    return False

nums = [3,5,1,4,3,1,4,3,1,4,3,9,6,1]
m = 3
k = 2
print(solve(nums, m, k))

入力

[3,5,1,4,3,1,4,3,1,4,3,9,6,1], 3, 2

出力

True

計算量と補足

この実装では、各開始位置 i に対して長さ m*k の配列比較を行うため、時間計算量は O(n × m × k)(n は配列の長さ)となります。なお、Pythonでは範囲外のスライスが自動的に切り詰められるため、i が大きい場合は sub1 と sub2 の長さが異なり、単純に False となるだけでエラーは発生しません。より効率化したい場合は、ループ範囲を range(len(nums) - m*k + 1) に変更することで、無駄な比較を省くことができます。