Pythonで配列内に積がkとなる部分配列が存在するかどうかを判定する方法

問題の概要

正の数と負の数が混在する配列 nums と、もうひとつの値 k が与えられます。このとき、要素の積がちょうど k になる部分配列(連続する要素からなる配列)が nums の中に存在するかどうかを判定します。

たとえば、nums = [-2, -1, 1, 3, 5, 8]、k = 6 という入力の場合、部分配列 [-2, -1, 3] の積は (-2) × (-1) × 3 = 6 となるため、出力は True になります。

アルゴリズムの考え方

この問題は、「最大積部分配列」を求める際によく使われるテクニックと同じ発想で解くことができます。ポイントは、負の数を掛けると積の符号が反転し、それまでの最大値と最小値が入れ替わるという性質です。この性質を利用して、各時点における積の最大値と最小値を追跡しながら処理を進め、そのどちらかが k に一致した時点で True を返します。

具体的な手順

1. minimum と maximum を nums[0] で初期化します。
2. prod_max(これまでの最大積)も nums[0] で初期化します。
3. i を 1 から配列の末尾まで繰り返します。
   • nums[i] が負の場合、maximum と minimum を入れ替えます。
   • maximum := max(nums[i], maximum × nums[i])
   • minimum := min(nums[i], minimum × nums[i])
   • minimum または maximum が k と等しければ True を返します。
   • prod_max := max(prod_max, maximum)
4. ループが終了しても見つからなければ False を返します。

なぜ負の数で最大値と最小値を入れ替えるのか?

負の数を掛けると積の符号が反転するため、それまでの「最大の積」は最小に、「最小の積」は最大になります。この入れ替えを毎回行うことで、任意の位置において「そこまでの要素で作れる積の最大値」と「最小値」を常に正しく追跡できるのです。

実装例(Pythonコード)

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

def solve(nums, k):
    minimum = nums[0]
    maximum = nums[0]

    prod_max = nums[0]

    for i in range(1, len(nums)):
        if nums[i] < 0:
            maximum, minimum = minimum, maximum

        maximum = max(nums[i], maximum * nums[i])
        minimum = min(nums[i], minimum * nums[i])

        if minimum == k or maximum == k:
            return True

        prod_max = max(prod_max, maximum)
    return False

nums = [-2, -1, 1, 3, 5, 8]
k = 6
print(solve(nums, k))

入力

[-2, -1, 1, 3, 5, 8], 6

出力

True

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加で必要なメモリは定数個の変数のみなので空間計算量は O(1) となります。すべての部分配列を総当たりで調べる O(n²) の方法と比べて非常に効率的です。