LeetCodeのTwo Sum解いてみた

始めに

今回もLeetCodeの有名問題Two Sumに挑戦してみようと思う
有名とは言えお恥ずかしながらコーディング面接やコーディングテストを受けた経験がないので実際によく出るよ！みたいなのはよくわからない。

ちなみにこの問題の難易度はEasyなので確実に突破したい

チャレンジしたい人は↓から挑戦してみて

問題

この問題は数値が格納された配列numsが渡されるので

解法1

まずはブルートフォースで解いてみる

簡単に思い付くがやはり非効率かな...

計算量は最悪の場合O(N2) となります。
一応、Acceptedはできるがパフォーマンスはよろしくない。
ただ、コーディング面接とかで最適な解法が見つからなかったら最悪この方法でも答えに辿り着いた方が良さそう。
この辺の対応は有識者の方がいれば教えて頂きたい🙇‍♂️

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)-1):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

解法２

今回もハッシュマップを使って解く
この方法なら計算量O(N) で解くことができる。
コーディング面接などで最も多く出題される分野みたいなので絶対に抑えておきたい。

ハッシュマップに保存する内容はnumsの各値とそのインデックス番号を保存する。

nums = [2,7,11,15]の場合、
↓こんな感じ
{2: 0, 7: 1, 11: 2, 15: 3}

もう一度、numsを探索し、nums[i]の補数(complement)がhash_map内にあれば、現在のiと補数のインデックス番号を配列で返せばOK。

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i in range(len(nums)):
            hash_map[nums[i]] = i

        # ハッシュマップ内に補数があるか探索
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hash_map and hash_map[complement] != i:
                return [i, hash_map[complement]]

        return []

感想

LeetCodeの回答にはライブラリを使い、1行で解決してるものもあったがコメント欄見る限り、あまり推奨されない方法らしい。
まあ、コーディング面接でライブラリ使って終わりだと面接にならないからね...
とはいえ実際の実務の現場では車輪の再発明は御法度とするため知識として持っているのは良いことだと感じた。
ハッシュマップなどで回答した上で、このような方法もあります。と+αの知識を添えると評価されるかも？

今回の問題はただハッシュマップに保存するだけでなく、補数を探索するという洞察力がないと難しかった。
道のりは険しそう