One-pass Hash Table

f:id:MDaiki:20210207003811p:plain

はじめに

LeetCodeのTwoSumという問題で、One-pass Hash Tableというアルゴリズムを知ったのでまとめます。

One-pass Hash Table

概要

One-pass Hash Tableとは、ハッシュテーブルを使用した探索方法です。候補の数値をkeyとして候補の数値が格納されていた要素数を格納します。

具体的な実装

候補配列Xと目標値Yが与えられます。
X=[2, 7, 11, 15]
Y=9

HashMapを定義してXの値を順番にKeyにして要素番号をinsertします。 するとHashMapは下記のようになります。

HashMap = {  
[2, 0],  
[7, 1],  
[11, 2],  
[15, 3],  
}  
※[Key, 代入した値]  

次にfor文を使用します。  
for 1回ループ {  
    探してる値 = 目標値Y - X[i]  
    HashMap[探してる値]  // これがnullじゃなかったら、探してる値が見つかったということ  
}

C++での実装

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int,int> hashMap;
  for(int i=0; i<nums.size();i++) {
    hashMap[nums[i]] = i;
  }

  for(int i=0; i<nums.size();i++) {
    if( i != hashMap[target-nums[i]] &&
      hashMap[target-nums[i]] != 0) {
        return {i, hashMap[target-nums[i]]};
    }
  }
  return {-1};
}

int main(){
  vector<int> nums = {2,7,11,15};
  int target = 9;

  vector<int> ans = twoSum(nums,target);

  for(int i = 0; i < ans.size(); i++){
    cout << ans[i] << endl;
  }
}

unordered_mapとmapの違い

c++で実装してみて、mapでよくね?って考えたが調べてみると実装はできるが計算量がunordered_mapのほうが少ないということがわかった。 mapは衡二分探索木で実装している。そして、unordered_mapはハッシュテーブルで実装している。

mapを使用するときに、Keyの順番を保持したいときはmapを使用する。それ以外は、ハッシュテーブルのunordered_mapを使用すれば良い。

終わりに

最初は、Brute Force(全探索)でTwoSumを答えてたけど計算量がO(n2)だからあまりよろしくないのだとわかった。

One-pass Hash TableはO(n)なのでこういう問題はこの探索法を使う!