10.4 ハッシュ最適化戦略¶
アルゴリズム問題において、線形探索をハッシュベースの探索に置き換えることで、アルゴリズムの時間計算量を削減することがよくあります。アルゴリズム問題を使用して理解を深めましょう。
Question
整数配列numsと目標要素targetが与えられ、配列内で「和」がtargetに等しい2つの要素を探索し、それらの配列インデックスを返してください。任意の解が受け入れられます。
10.4.1 線形探索：時間を空間と交換¶
すべての可能な組み合わせを直接横断することを考えてみます。下図に示すように、ネストしたループを開始し、各反復で2つの整数の和がtargetに等しいかどうかを判断します。そうであれば、それらのインデックスを返します。
図 10-9 Linear search solution for two-sum problem
コードは以下の通りです：
この方法の時間計算量は\(O(n^2)\)、空間計算量は\(O(1)\)で、大容量データでは非常に時間がかかる可能性があります。
10.4.2 ハッシュ探索：空間を時間と交換¶
ハッシュテーブルの使用を考えてみましょう。キーと値のペアはそれぞれ配列要素とそのインデックスです。配列をループし、各反復中に下図に示すステップを実行します。
- 数値
target - nums[i]がハッシュテーブルにあるかどうかを確認します。ある場合は、これら2つの要素のインデックスを直接返します。 - キーと値のペア
nums[i]とインデックスiをハッシュテーブルに追加します。
図 10-10 Help hash table solve two-sum
実装コードは以下に示され、単一のループのみが必要です：
two_sum.cpp
/* 方法二：補助ハッシュテーブル */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
int size = nums.size();
// 補助ハッシュテーブル、空間計算量はO(n)
unordered_map<int, int> dic;
// 単層ループ、時間計算量はO(n)
for (int i = 0; i < size; i++) {
if (dic.find(target - nums[i]) != dic.end()) {
return {dic[target - nums[i]], i};
}
dic.emplace(nums[i], i);
}
return {};
}
two_sum.java
/* 方法二: 補助ハッシュテーブル */
int[] twoSumHashTable(int[] nums, int target) {
int size = nums.length;
// 補助ハッシュテーブル、空間計算量は O(n)
Map<Integer, Integer> dic = new HashMap<>();
// 単一層ループ、時間計算量は O(n)
for (int i = 0; i < size; i++) {
if (dic.containsKey(target - nums[i])) {
return new int[] { dic.get(target - nums[i]), i };
}
dic.put(nums[i], i);
}
return new int[0];
}
この方法は、ハッシュ探索を使用することで時間計算量を\(O(n^2)\)から\(O(n)\)に削減し、実行時効率を大幅に向上させます。
追加のハッシュテーブルを維持する必要があるため、空間計算量は\(O(n)\)です。それにもかかわらず、この方法は全体的により均衡のとれた時空間効率を持ち、この問題の最適解となります。