個人的アルゴリズムの勉強の部屋

アルゴリズムを書くトレーニングを何ヶ月かにやってるのですが
一人で黙々とやるのが続かないので記事にしてなんとかモチベーションを
保つという目的で書いていきます。

問題：配列の中の二つ数字の組み合わせの和で、指定した数字に一致した場合、True。一致しなかった場合、Falseになるような関数を作る。

input

from typing import List
>> array:List[int],dist:int

output

もしarrayの中の二つの組み合わせを使用してdistになるものがあればTrue。それ以外False

一般的な解き方：for文で探索するやつ

from typing import List
def findpair(arr:List[int], dist:int) -> bool:
    for i in range(len(arr)):
        for j in range(i+1 ,len(arr)):
            if arr[i] + arr[j] == dist:
                return True
    return False

インテリジェントな解き方

from typing import List

def findpair(arr:List[int], dist:int) -> bool:
    arr.sort()
    left = 0
    right = len(arr)-1
    while left < right:
        if arr[left] + arr[right] == dist:
            return True
        elif arr[left] + arr[right] > dist:
            return right -=1
        else:
            return left +=1
    return False

ハッシュテーブルを使用した解き方

from typing import List

def findpair(arr:List[int], dist: int) -> bool:
    hash = {}
    for num in arr:
        if hash[dist-num]:
            return True:
        else:
            hashed[num] = True
    return False