LeetCode 1. Two Sum を完全に理解する by TypeScript

Two Sum by TypeScript

転職したいな〜と思ってLeetCodeはじめました。
しかし、まったく歯が立たない。

普段はReactとかSvelteとかExpressとかPrismaとかいろいろやってます。
僕の場合、フロントエンドは関数型の考え方(ramda.jsなど)で解くことが多いです。
アルゴリズムなどは不勉強で、結構ゴリゴリループを回しがちなので、計算量なども意識できるようになればいいな、と思ってはじめました。
本当に問題文からわからない人向けに噛み砕いて書いてみました。

今回はこの問題を解きます。
https://leetcode.com/problems/two-sum/

問題文

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.

日本語 by DeepL

整数numsの配列と整数targetが与えられたとき、2つの数値の足し算がtargetになるようなインデックスを返せ。
各入力は正確に1つの解を持つと仮定してよく、同じ要素を2度使ってはならない。
また、同じ要素を2度使ってはならない。解答はどのような順序でも返すことができる。

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

答えが9になる組み合わせを探して、そのindexを返すということ。
2と7を足したら9になるから2のindex = 0 と7のindex = 1を返せばよろしい。

検討

ごくごく普通に考えるとループしていって、2と7を足してみてOKならそのindexを返す
2と11足してダメならやめて……とやっていったら良さそうだ。
けど、無駄な計算があるかもな……と思う。
ということで回答・解説としては以下になる。

回答

function twoSum(nums: number[], target: number): number[] | null {
  /*
    step1: new Map()で空のMapを作成する。
    Mapの詳しい解説はhttps://ja.javascript.info/map-set
    key:valueペアを入れられるもの。
    indicesってなんやねん、というと
    indexの複数形らしい。
  */
  const indices = new Map();

  /* 
    step2: for文でnumsの要素を一つずつ取り出す。
    あと今回の数字をわかりやすくcurrentNumとしておく。
  */
  for (let index = 0; index < nums.length; index++) {
    const currentNum = nums[index];

    /* 
      step3: target - currentNumということで、
      たとえばtargetが9のとき、currentNumが2だったら、7となる。
      もしtargetが9でcurrentNumが3だったら、6となる。
      complementとは、補完するという意味。
      今回のループの数字(currentNum)と足してtargetになる数をcomplementという。
    */
    const complement = target - currentNum;

    /* 
      step4: complementがindicesにあるかどうかを確認する。
      もしあれば、それが答えになる
      最初のループでは、complementは7(9-2)で、indicesには何も入っていないので飛ばす。

      2回目のループでは、complementは2(9-7)である。
      そして、1回目のループでMapに [2,0]がセットされている。
      返さないといけないのは最初のループで入れた2のindexと、
      今回のループで入れた7のindexである。
      だからMapから今回のcomplementである2というkeyからvalueのindex(0)を取り出す。
      そして、今回のループのindex(1)を返す。
      ということで答えは[0,1]となる。
    */
    if (indices.has(complement)) {
      return [indices.get(complement), index];
    }

    /* 
      step5: complementがindicesにない場合は、
      indicesにcurrentNumとindexをセットする。
      つまり、keyにcurrentNum(今回の数字)
      valueにindex(今回の数字の位置)をセットする。
      最初のループでは、indicesには[2,0]がセットされる。
    */
    indices.set(currentNum, index);
  }
  return [];
}

一度読んで理解できたら、コメントだけ残してソースコードを消す。
そしてコメントを参考にソースを書いてみる。
それを繰り返して正しいソースが書けるようになったら、コメントも消してゼロからコードを書く。
こんな感じで理解しつつ覚える……というのをやってきます。たぶん……。

普段、フロントエンドでforループをほとんど書かないので、なかなか大変です。