Pythonでソート済みリストから2つの数の合計がkになるか判定するプログラム

昇順にソートされた数値リスト nums と、別の値 k が与えられているとします。このとき、リストから選んだ2つの要素の合計が k と一致するかどうかを判定する必要があります。要素には負の数や0も含まれる可能性があります。さらに、この問題は定数のメモリ領域(空間計算量 O(1))で解くことが求められます。

例として、nums = [-8, -3, 2, 7, 9]、k = 4 の場合、出力は True になります。これは、7 と -3 を選ぶと 7 + (-3) = 4 となり、k と一致するためです。

解法のアプローチ:二ポインタ法

この問題は「二ポインタ(two-pointer)テクニック」を使うことで効率的に解けます。リストがすでにソートされていることを利用し、先頭と末尾にそれぞれポインタを配置し、合計値の大小に応じてポインタを動かしていくのがポイントです。

具体的な手順は以下の通りです。

• i := 0(先頭のインデックス)
• j := リストの長さ - 1(末尾のインデックス)
• i < j の間、以下を繰り返します。
  • cur_sum := nums[i] + nums[j]
  • cur_sum が k と等しければ True を返す
  • cur_sum が k より小さければ i を1増やす(合計を大きくする)
  • それ以外の場合は j を1減らす(合計を小さくする)
• ループが終了したら False を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums, k):
    i = 0
    j = len(nums) - 1
    while i < j:
        cur_sum = nums[i] + nums[j]
        if cur_sum == k:
            return True
        elif cur_sum < k:
            i += 1
        else:
            j -= 1
    return False

nums = [-8, -3, 2, 7, 9]
k = 4
print(solve(nums, k))

入力

[-8, -3, 2, 7, 9], 4

出力

True

計算量について

このアルゴリズムでは、各ステップで必ずどちらかのポインタが移動するため、最悪でもリストの長さ分だけ繰り返しが行われます。したがって、時間計算量は O(n)、追加のデータ構造を使わないため空間計算量は O(1) となり、「定数のメモリ使用量で解く」という制約も満たしています。