LeetCode - 1. Two Sumを解く - やめられないやめられない

とあるブログを見てみてだいぶ感動したので一つだけマネして、LeetCodeを始めてみた。やってみてだいぶレベルが足りないのを確認してとりあえず凹む。
とあるブログとはこちら

ガチ三流エンジニアが米国マイクロソフトのドリームチームのメンバーになれた話とそのためにやった事 - メソッド屋のブログ

問題へのリンク

解答

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    candidates = nums.select { |num| num < target }
    candidates.map.with_index do |c1, index1|
        candidates.map.with_index do |c2, index2|
            return [index1, index2] if (target - c1 == c2)
        end
    end
end

時間制限超過して失敗。ブルードフォースで計算量O(n²)で書かれていた。これではダメなやつ。

修正

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    h = {}
    nums.each_with_index do |n1, index1|
        h[n1] = index1
    end
    nums.each_with_index do |c2, index2|
        tmp = target - c2
        next if h[tmp].nil? || index2 == h[tmp]
        return [index2, h[tmp]]
    end
end

あとでブログ書き直しつつ復習しよう。

参考にさせていただいた記事

https://euro.qrunch.io/entries/IMtqWEs4GTw6XJCf