[Python] 2 Sum問題

2 Sum問題

与えられた整数配列Aと1つの整数Kに対して, Aの中からその合計値がKとなるような 2つの整数を見つけ, その2つを返却せよ. （条件を満たす2つの整数は, 必ず配列A内に1組だけ存在するものと考えて良い）

入力: numbers={2, 7, 11, 15}, target=9 出力: [1, 2]

アルゴリズム1000本ノック #7. 2 Sum

総当たり

全ての組み合わせを総当たりでチェックします。

計算量は\( O(n^2)\)、空間量は\( O(1) \)となります。

def two_sum_brute_force(nums, target):
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
    return False

ハッシュを使う

入力: numbers = {2, 7, 11, 15}とtarget=9 をもとに、辞書 {(9-2):2, (9-7):7, (9-11);11, (9-15):15} を作ります。最初から数字を見ていき、辞書のkeyの中に今見ている値があれば、その数字を返却します。

計算量は\( O(n)\)、空間量は\( O(n) \)となります。

def two_sum_hash_table(nums, target):
    hashmap = dict()
    for i in range(len(nums)):
        if nums[i] not in hashmap:
            hashmap[target - nums[i]] = nums[i]
        else:
            return [hashmap[nums[i]], nums[i]]       
    return False

ソートして両端から見ていく

数字がソートしてあれば、両端から見ていくことで、空間量を減らすことができます。

計算量は\( O(n)\)、空間量は\( O(1) \)となります。

def two_sum(nums, target):
    i = 0
    j = len(nums) -1

    while i <= j:
        if nums[i] + nums[j] == target:
            return[nums[i], nums[j]]
        elif nums[i] + nums[j] < target:
            i += 1
        elif nums[i] + nums[j] > target:
            j -= 1
    return False