Pythonで解く「kと-kの両方が存在する最大のkを見つける」問題

この記事では、Pythonを使って「リスト内に k と -k の両方が存在するような、最大の数 k を見つける」問題の解き方を解説します。

問題の概要

数値のリスト nums が与えられたとき、k と -k がどちらもリスト内に存在するような最大の数 k を求めます。該当する要素が存在しない場合は -1 を返します。

たとえば、入力が [-5, 2, 9, -6, 5, -9] の場合、「9」と「-9」が両方存在するため、答えは 9 となります。

解法のアプローチ

この問題は、リストを正の数と負の数に分けてソートし、対応するペアを効率的に探すことで解けます。具体的な手順は以下の通りです。

• L1:nums 内の 0 以上（正）の要素だけを集めたリストを作る
• L2:nums 内の 0 以下（負）の要素だけを集めたリストを作る
• L1 を降順にソートする
• L2 を昇順にソートする
• L1 の各要素 i について、L2 の各要素 j と比較する
  • i + j == 0 ならば、i を返す（これが現時点での最大値）
  • i + j > 0 ならば、内側のループを抜けて次の i へ進む
• ループが完了しても見つからなければ、-1 を返す

ポイントは、L1 を降順・L2 を昇順に並べることで、大きい方から順にペアをチェックできる点です。i + j が正になった時点で、それより小さい j との組み合わせでは絶対に 0 にならないため、内側のループを打ち切ることで無駄な計算を省いています。

実装例

以下がPythonでの実装コードです。

class Solution:
    def solve(self, nums):
        L1 = [i for i in nums if i >= 0]
        L2 = [i for i in nums if i <= 0]
        L1.sort(reverse=True)
        L2.sort()
        for i in L1:
            for j in L2:
                if i + j == 0:
                    return i
                elif i + j > 0:
                    break
        return -1

ob = Solution()
nums = [-5, 2, 9, -6, 5, -9]
print(ob.solve(nums))

実行結果

入力:

[-5, 2, 9, -6, 5, -9]

出力:

9

補足：より効率的な方法

上記の二重ループ方式は分かりやすい反面、最悪の場合 O(n²) の計算量がかかります。集合（set）を使えば O(n) まで改善できます。

def solve(nums):
    s = set(nums)
    result = -1
    for x in s:
        if -x in s:
            result = max(result, x)
    return result

まずリストをセット化し、各要素 x について「-x も存在するか」を確認します。条件を満たすものの中で最大値を採用すれば、同じ答えをより高速に得られます。データサイズが大きい場合はこちらの方法がおすすめです。