出力結果

[ [ 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」を記録。

２回目のループで「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を支えているアルゴリムも登場。名著中の名著。