1. Two Sum (Easy)

公開日:2019-02-27
最終更新:2019-02-27

https://leetcode.com/problems/two-sum/

数値の配列とターゲットの数値が与えられて、足すとターゲットの数値になる2つの数値の組み合わせを求めよという問題。回答は2つの数字のインデックスを配列で返す。
与えられる数値群は必ず一意に答えが得られると仮定してよい。同じ要素は二度使用しない。

とりあえず愚直に全部順番に足してみて、ターゲットと一致したら返すコードを書いて通した。

自分の回答

# @param {Integer[]} nums  
# @param {Integer} target  
# @return {Integer[]}  
def two_sum(nums, target)  
    for i in 0..nums.size-1 do  
        for j in 0..nums.size-1 do  
            next if i == j  
            two = nums[i] + nums[j]  
            return [i, j] if two == target  
        end  
    end  
end

こういうのもブルートフォースでのアプローチと呼ぶらしい。
ただしこのままでは時間計算量がO(n^2)なので、Two-pass Hash Table と One-pass Hash Table というアプローチがある。

Two-pass Hash Table の実装

Two-passは一度全部の数値とインデックスをハッシュに格納しておき、そのあとcompelment(補数)となる数値を順番に求めていく。

# @param {Integer[]} nums  
# @param {Integer} target  
# @return {Integer[]}  
def two_sum(nums, target)  
    hash = {}  
    for i in 0..nums.size-1 do  
        hash[nums[i]] = i  
    end  
    for i in 0..nums.size-1 do  
        complement = target - nums[i]  
        if hash.has_key?(complement) && hash[complement] != i  
            return [i, hash[complement]]  
        end  
    end  
end

One-pass Hash Table の実装

One-passは順次補数の計算とハッシュへの格納を同時に行う。

# @param {Integer[]} nums  
# @param {Integer} target  
# @return {Integer[]}  
def two_sum(nums, target)  
    hash = {}  
    for i in 0..nums.size-1 do  
        complement = target - nums[i]  
        if hash.has_key?(complement)  
            return [hash[complement], i]  
        end  
        hash[nums[i]] = i  
    end  
end

時間計算量はそれぞれO(n)になる。(詳しくはSolutionを参照)

Algorithm Runtime Memory
Brute Force 7548 ms 9.6 MB
Two-pass Hash Table 36 ms 10.3 MB
One-pass Hash Table 36 ms 10.1 MB

ハッシュテーブルを使うと大幅に実行時間が短縮されていることがわかる。

記事が少しでもいいなと思ったらクラップを送ってみよう!
36
+1
https://leetcode.com/ の Problems の解法を載せています。ネタバレ注意。

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする