リストから与えられた合計のペアを集合を利用してチェックする。

問題

リストとある値が与えられたとき、リストの中に、合計がある値に一致するペアを見つけるという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)

前回の実装とは異なり、今回はハッシュ(set)を使った方法でチャレンジする。

実装

setを使った方法でチャレンジするが、そもそもどうやってsetを有効に活用すればよいかを考える。今回の場合だと、ターゲットが16だとして、13, 2, 5, 9, 12, 7と数値のリストが渡されたときに、ターゲットからループされる値を引いたもの集合から検索し、なければ集合に保存。それを繰り返して、ペアを発見していく。

つまり、今回の例であれば、まずは13を集合に保存し、2を集合に保存し、5を集合に保存し、というように繰り返すと、7のループの前には、{2,5,9,12,13}という集合の状態になるので、7のループの際には、16-7=9となって、9を集合から検索して一致するので、(9, 7)を返すことで、ターゲットのペアとなる組み合わせを返すことができる。

from typing import List, Tuple, Optional

def hasTwoCandidates(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
    cache = set()
    for number in numbers:
        value = target - number
        if value in cache:
            return (value, number)
        cache.add(number)


if __name__ == '__main__':
    numbers = [13, 2, 5, 9, 12, 7]
    print(hasTwoCandidates(numbers, target=16))

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

(9, 7)
(13, 3)

集合の基本

今回のような例で集合を使うメリットは、重複を集合は保存しないという性質があるため。集合の基本的な演算は下記の通り。

a = {1,2,2,3,4,4,4,4,5}
print(a)
{1, 2, 3, 4, 5}

print(type(a))


# Setの演算
b = {2, 4, 6}
print(a - b)
{1, 3, 5}

# 論理積
print(a & b)
{2, 4}

# 排他
print(a ^ b)
{1, 3, 5, 6}

# 論理和
print(a | b)
{1, 2, 3, 4, 5, 6}

他にも、要素の追加や削除、集合のクリアなどもできる。

s = {1,2,3,4,5}

# 要素の追加
s.add(6)
print(s)
{1, 2, 3, 4, 5, 6}

# 要素の削除
s.remove(6)
print(s)
{1, 2, 3, 4, 5}

s.clear()
print(s)
set()