リストから与えられた合計のペアをチェックする

問題

リストとある値が与えられたとき、リストの中に、合計がある値に一致するペアを見つけるというGiven an array 'A' and a number x, check for pair in 'A' with sum as xの問題。下記の例では-3+1=-2となるので、(-3, 1)というペアを返さればOK。

input: [0, -1, 2, -3, 1]
target: -2
output: (-3, 1)

実装

考え方としては、リストの左からまず1つの値を固定し、インデックスをずらしながら、ペアごとにターゲットに一致するかを確認すればよさそうだけど、解法を見ると、ソートしてからの挟み撃ちを行っている。

画像を見たほうが早いけど、ターゲットが2つの要素の合計よりも大きい場合は、必要な合計の値を増やすために左ポインタをシフトして、合計がターゲットよりも小さい場合は、値を減らすために右ポインタをシフトしていきます。こうすることで、効率よく探索できるとのこと。

画像はソートされた状態です。画像の例だと、1番大きい値と、1番小さい値を合計しても、ターゲットよりも小さいのであれば、値を増やす必要があることがわかるので、左のポインタをシフトさせる。そして、1番大きい値と、2番目に小さい値を合計して、ターゲットよりも大きくなるのであれば、 値を減らす必要があるので、右のポインタをシフトさせる。

from typing import List, Tuple, Optional

def hasTwoCandidates(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    len_numbers = len(numbers)
    numbers.sort()
    left = 0
    right = len_numbers - 1

    while left < right:
        if numbers[left] + numbers[right] == target:
            return (numbers[left], numbers[right])
        elif numbers[left] + numbers[right] < target:
            left += 1
        else:
            right -= 1
    return ()


numbers = [13, 2, 5, 9, 12, 7]
print(hasTwoCandidates(numbers, 16))

numbers = [13, 2, 5, 9, 12, 7]
print(hasTwoCandidates(numbers, 20))

numbers = [13, 2, 5, 9, 12, 7]
print(hasTwoCandidates(numbers, 50))

(7, 9)
(7, 13)
()

次回は、この問題をハッシュを使った方法で解いてみる。