RubyでLeetCodeやってみる-TwoSum

#概要
プログラミング力を上げるためにLeetCode始めました。
基本問題TwoSumの解説をRubyで行っていきます。

#Two Sum
##問題
整数の配列を与え、2つの要素の和がターゲットの値となるインデックスの組み合わせを配列で返す。

##例

nums = [2,7,11,15]
target = 9

が与えられるとします。

nums[0] + nums[1] = 2+7 = 9 

なので

[0, 1]

を返します。

上記を満たすようなメソッドをRubyで書くことを目標とします。

##解法1 【Brute Force】
Brute Forceとは日本語で"強引な"という意を示します。
つまり何も考えずに解きます。

# @param {Integer[]} nums 整数の配列
# @param {Integer} target 整数
# @return {Integer[]} 整数の配列

def two_sum(nums, target)
  (0..nums.length-1).each do |i|
    (i+1..nums.length-1).each do |j|
      return [i, j] if nums[i] + nums[j] == target #目標値となるかチェック
    end
  end
end

ある要素を基準にして、それ以降の要素を探索しながら和が目標値になるか見ていきます。

このコードを提出すると次のような結果になります。

Runtime : 4656 ms(平均)
Memory : 9.6 MB(平均)

平均は大体上の値になりますが、たまにタイムリミットになります。(提出物としてはアウト)

これはeachによって平均n回×n-1回計算が行われるため計算量オーダーはO($n^2$)で示されます。
すなわち要素数が多くなるほど二次関数的に時間を必要とします。

##解法2 【Two-pass Hash Table】
和が目標値になる要素を探すよりも、目標値-要素1となる補数が存在するかを探した方が効率的になります。
そこで使われるのがハッシュです。

# @param {Integer[]} nums 整数の配列
# @param {Integer} target 整数
# @return {Integer[]} 整数の配列

def two_sum(nums, target)
  hash = {}
  (0..nums.length-1).each do |i|
    hash.store(nums[i], i) #ハッシュを初期化
  end
  (0..nums.length-1).each do |i|
    complement = target - nums[i] #補数を用意
    return [i, hash.fetch(complement)] if hash.has_key?(complement) && hash.fetch(complement) != i #補数チェック
  end
end

あらかじめハッシュを用意しておき、補数となる値が格納されているか探索します。

このようにすることでeachによるn回×n-1回の計算がn回だけになります。
よって計算量オーダーはO($n$)になります。
そしてこのコードを提出すると結果は次のようになります。

Runtime : 43 ms(平均)
Memory : 10.2 MB(平均)

若干メモリの使用量は増えましたが、恐ろしいほど早くなりました。

##解法3 【One-pass Hash Table】
今度は同じハッシュを使う方法でも技ありです。
一度の走査で完結します。

# @param {Integer[]} nums 整数の配列
# @param {Integer} target 整数
# @return {Integer[]} 整数の配列

def two_sum(nums, target)
  hash = {}
  (0..nums.length-1).each do |i|
    complement = target - nums[i]
    return [hash.fetch(complement), i] if hash.has_key?(complement) #補数チェック
    hash.store(nums[i], i) #補数が存在しなかったため追加
end

コードの量は減りましたが読みにくくなりました。
これは条件を満たす要素が見つからなかった場合に追加していく方法です。
一度の走査で要素の追加と探索を行うためメモリの量を少し削減できます。
同じく計算量オーダーはO($n$)となり、提出結果は次のようになります。

Runtime : 48 ms(平均)
Memory : 9.9 MB(平均)

若干遅くなりましたがメモリの使用量が減りました。
解法2と比較してどちらの方法が優れているかは状況次第ですが、
解法１と比較するとハッシュを用いる方法がどれだけ優れているか明らかだと思います！
また、試行回数が7回ずつのため平均値の精度が高いとは言えませんが、この結果を見ると歴然ですね。

#まとめ
LeetCodeの基礎問題であるTwoSumの解説を行いました。
また、適切な解法をとることによって実行時間を大幅に短縮することが分かりました。
この１つの問題をきちんと解くだけで様々なことが学べたと思います。
これからもLeetCode続けていきたい…