Pythonで2つリストの各要素合計と指定した値を比較する

はじめに

　2 つのリストがあったときに、その各要素の合計値と指定した値を比較したくなったことってありませんか？
　
　例えば、

　　[-1, 3, 8, 2, 9, 5]
　　[4, 1, 2, 10, 5, 20]

　という2つのリストがあるとします。

　その時、各リストからそれぞれ選んだ 2 つ要素の合計によって特定の値が表現できるかを調べます。

　もし、特定の値が 25 の時、(-1, 4) を選択した場合、合計は 3 なので違います。その場合は (5, 20) のみが正解です。
　
　この問題を解く方法がYouTubeの動画（下記のURL参照）で紹介されていました。今回はその方法をPythonで書きました。

プログラム

　紹介されていた方法の中から3つの解き方をプログラムしました。
　比較する値は 24, 25, 26 23, 24, 25です（2019年12月13日訂正）。

　まずは、全ての要素を足し合わせる方法です。

Brute-force.py

# リスト
A = [-1, 3, 8, 2, 9, 5]
B = [4, 1, 2, 10, 5, 20]

# 比較したい値
target = 24

# ブルートフォース
for i in A:
    for j in B:
        if target - 1 <= (i + j) <= target + 1:
            print(str(i) + "と" + str(j) + "はペアです。")

　次は、リストの中身を検索してから比較する方法です。

linear.py

# リスト
A = [-1, 3, 8, 2, 9, 5]
B = [4, 1, 2, 10, 5, 20]

# 比較したい値
target = 24

# 線形選択
for i, v in enumerate(B):
    if target - 1 - v in A:
        index = A.index(target - 1 -v)
        print(str(A[index]) + "と" + str(v) + "はペアです。")
    if target - v in A:
        index = A.index(target - v)
        print(str(A[index]) + "と" + str(v) + "はペアです。")
    if target + 1 - v in A:
        index = A.index(target + 1 - v)
        print(str(A[index]) + "と" + str(v) + "はペアです。")

　最後は、マトリックスを作成する方法です。比較する値は 12, 13, 14 です。

Matrix.py

# マトリックス作成
import numpy as np

# 要素
A = np.array([7, 4, 1, 10])
B = np.array([4, 5, 8, 7])

# 要素を昇順に並び替える
A.sort()
B.sort()

target = 13

# 全要素の足し算を表にする
array = np.array([i+j for i in A for j in B]).reshape((len(A), len(B)))

# ターゲットの範囲
column_start = 0            #0
column_end = array.shape[1] #4

# 探索
for j in reversed(range(array.shape[0])):
    #上側の範囲
    for i in range(column_start, column_end):  
        if array[i][j] >= target - 1:
            column_start = i
            break
    print(str(A[i]) + "と" + str(B[j]) + "はペアです。")

学んだこと

　どうすればより少ない計算量で問題を解くことができるのか学びました。

おわりに

　正直なところ、勉強不足で最後の方法の活用場面は分かりませんでしたが、
　これからもプログラミングの学習を続けていきたいと思います。
　
　ご覧いただきありがとうございました。

参考URL

　5 Problem Solving Tips for Cracking Coding Interview Questions (YouTubeの動画にリンクしてます)