【JavaScript】LeetCodeで計算量の改善とMapオブジェクトの活用方法を学んだことの共有
LeetCodeというサイトをご存知ですか？
コーディング面接で使われたり、出題されたものに類似した問題を解くことができる海外の学習サイトで日本でいうPaizaのようなサイトだと思います。
今まで名前だけ知っていたのですが、利用して気きませんでした。
現在転職活動真っ最中で技術テスト対策の相談をしたところ、メンターさんからLeetCodeをおすすめしていただいたので始めてみました。
LeetCodeの問題の難易度はEasy、Medium、Hardの三種類。
まずはEasyで腕試しと思ったら意外と難しかったです、、。
今回はtwoSumという問題を解いた際に、計算量やJavascriptのMapオブジェクトについて学んだことを共有したいと思います。
問題
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
- 整数が配列で格納されているので、配列内の値２つ足してtargetの値になる値のインデックスを返却する
- 同じ値１回しか使えない
- 返却する値の順番は問わない
、、、といった内容です。（多分）
例えば
Input: nums = [2,7,11,15], target = 9
の場合、
Output: [0,1]
という値を返却するようにします。
デフォルトで下記のコードが用意されています。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
};
一番てっとり早い解き方(非推奨)
for文を複数使って全パターン調べていく方法が一番簡単にできます。
var twoSum = function(nums, target) {
for (let i = 0; i <= nums.length; i++) {
for (let j = i + 1; j <= nums.length; j++) {
if (nums[i] + nums[j] == target) {
return [i, j]
}
}
}
};
この解き方のメリット
- 楽
- とりあえず解ける
この解き方のデメリット
- 配列が大きくなると計算量がとんでもないことになる
解説
この問題を解く時に真っ先に思い浮かんだ方法でした。
ただfor文のネストは計算量的にきっとあまり好ましくないよなーと思い、使わない方法を考えました。
※ネストされたfor文を使用する解法の計算量はO(n^2)となり、配列のサイズnが大きくなるにつれて、実行時間が二乗で増加するため、大規模なデータでは非効率的になってしまう。
LeetCodeで提出後のスコアをみてもテストは合格していますがRuntimeは悪いことがわかります。
for文のネストを避けた解き方（これも非推奨） - indexOfメソッド使用
for文のネストを避けるためにindexOfを使って解いてみました。
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++) {
const pair = target - nums[i];
const index = nums.indexOf(pair , i + 1)
if(index !== -1) {
return [i, index]
}
}
};
この解き方のメリット
- ネストされたfor文を使用せず、計算量がO(n)に改善された
この解き方のデメリット
- indexOfメソッドの内部で線形探索(リニアサーチ)※が行われるため、実際の計算量はO(n^2)に近い
※線形探索(リニアサーチ)：配列の先頭から順番に目的のデータを探していくアルゴリズム
解説
ネストされたfor文を避けることで計算量が改善されました。
が、LeetCodeの他ユーザーと比べてRuntimeが平均より悪い結果になりました。
indexOfのデメリットで述べたようにindexOfメソッドでは配列（データ）が大きい場合、計算量が増えてしまい、大幅な改善にはなりませんでした。
なので他ユーザーの解法を参考にします。
他の方の解法を参考に今回提出したコード - Mapオブジェクト（ハッシュマップ）使用
Runtimeが短い解法を見たところ、Mapオブジェクト（ハッシュマップ）を使用していました。
※Mapオブジェクト（ハッシュマップ）とは
Mapはマップ型のコレクションを扱うためのビルトインオブジェクトです。 マップとは、キーと値の組み合わせからなる抽象データ型です。 他のプログラミング言語の文脈では辞書やハッシュマップ、連想配列などと呼ばれることもあります。
引用元
ということでMapオブジェクトを使用してみます。
var twoSum = function(nums, target) {
const map = new Map();
for(let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if(map.has(complement)) {
return[map.get(complement),i]
}
map.set(nums[i], i);
}
};
この解き方のメリット
- 時間計算量を O(n) に改善できる
この解き方のデメリット
- やや複雑に感じる
解説
Mapを使用することで、配列の各要素とそのインデックスのペアを保持します。
各要素に対し、【target - 現在の要素】の値がMapに存在するかを確認します。
存在する場合はペアが見つかったことになるので、Mapから保持しているインデックスを取得し、現在のインデックスとともに返却します。
存在しない場合は、現在の要素とインデックスをMapに追加し、次の要素の処理に進みます。
Mapの検索はO(1)で行えるため、全体の計算量はO(n)に抑えられ、効率的に解くことができます。
...らしい。
実際にRuntimeを確認してみるとindexOfを使用した解法よりも改善されていることがわかりました。
まとめ
Easy問題でしたが勉強になることがたくさんありました。
Mapオブジェクトは使ったことはあるけれど、getメソッドやhasメソッドなどあまり知らないメソッドもあったのでもっと勉強が必要だと思いました。
計算量について意識することと、普段何気なく使ってしまっているビルトインオブジェクやメソッドを詳しくなることがエンジニアとして一人前になる為の一歩なのかなと思いました。
Discussion