【アルゴリズム】Googleの問題が解けるか?合計値になる組み合わせを探せ。
出力結果
[ [ 6, 1 ], [ 3, 4 ] ]
問題自体は難しくないですね。合計をなる組み合わせを、配列として返せばいいわけです。ただ、効率的に解こうとすると一工夫いります。
この問題は有名で、Youtubeにアップされている、Googleの面接例にも登場します。動画の場合、戻り値はtrue/falseですが、考え方は一緒です。
みなさんも、チャレンジしてみよう。
ナイーブな実装例 O(n^2)
function twoSum(numArray, sum) {
var pairs = [];
for (let i = 0; i < numArray.length; i++) {
for (let j = 1; j < numArray.length - 1; j++) {
var currNum = numArray[i] + numArray[j];
if (currNum === sum) pairs.push([numArray[i], numArray[j]]);
}
}
return pairs;
}
//console.log(twoSum2([1, 6, 4, 5, 3], 7));
これはパッと思い浮かぶ方法だと思います。が、データ量が増えたら、計算量はとんでもないことに。。
実装例 O(n)
function twoSum(numArray, sum) {
var pairs = [];
var hashTable = [];
for (let i = 0; i < numArray.length; i++) {
var currNum = numArray[i];
var couterpart = sum - currNum;
if (hashTable.indexOf(couterpart) !== -1) {
pairs.push([currNum, couterpart]);
}
hashTable.push(currNum);
}
return pairs;
}
//console.log(twoSum([1, 6, 4, 5, 3], 7));
これはO(n)になる、効率的な方法です。動画だと最終的にこの解法です。これでいきたいですね。
ポイントとなるのは、組み合わせなので、別の配列に片割れを、記録していくことです。例では、hashTableに記録します。
「7」を探したいとすると、配列の最初が「1」なので、7-1=6。
6はhashTableに、ないので「1」を記録。
2回目のループで「6」が登場。7-6=1 で「1」はすでに登場しているので、組み合わせを発見!
配列の位置を返すパターン
var twoSum = function(num, target) {
var map = {};
for (let i = 0; i < num.length; i++) {
map[num[i]] = i;
}
for (let i = 0; i < num.length; i++) {
var index = map[target - num[i]];
if (index) {
return [i, index];
}
}
return [];
};
//console.log(twoSum([2, 3, 7, 11], 9));
どうでしたか? 単純な問題ですが、奥は深いと思います。データ構造でひと手間かけるだけで、高速なアルゴリズムが書けてしまいます。
プログラムなんてググれば、なんでも出てきます。それでいいと思います。
今の時代、何かを知っていることって、そんなに価値はないです。
逆に、今回の動画を見ていて思うのですが、「なぜそうなったか?」プロセスを、説明できると貴重です。
全ての知識が、クラウド上に出揃った時代、最後に残るのは、自分の考えを、わかりやすく説明できるスキルなのかもしれません。
Googleを支えているアルゴリムも登場。名著中の名著。
この記事が気に入ったらサポートをしてみませんか?