📖
LeetCodeのTypeScript解説
Two Sum
ポイント
- 合計する数値の数は2つのみであること。（3つ以上は考慮不要）
function twoSum(nums: number[], target: number): number[] {
let tmpMap = new Map();
for (let i = 0; i < nums.length; ++i) {
// ターゲット値から現要素の値を引いた数値がMapに存在すれば終わり。
if (tmpMap.has(target - nums[i])) {
return [tmpMap.get(target - nums[i]), i];
}
// 現在の要素の値
tmpMap.set(nums[i], i);
}
return [-1, -1];
}
解説
let tmp = new Map();
Mapはキーと値のペアでデータを管理できる多次元配列に似たコレクション。多次元配列と違う点は次の通り。
- キーは文字列以外の型（数値やオブジェクトなど）が使用可能。
- 要素の順番を保持してくれる。
- 要素数が増えても検索速度は一定。（多次元配列は要素数に比例して検索速度が変わる）
tmpMap.has(key);
特定のキーに対する要素がMapオブジェクト内に存在していたら、trueを返す。さもなければ、falseを返す。
つまり、Mapオブジェクトにどんどん数値をキーとしてセットしていく。ターゲット値から現在の要素を引いた数が、Mapオブジェクトに存在するなら、その2つのインデックスを返せばよい、ということ。
Add Two Numbers
ポイント
- シングル数値ノードリンク
シングル数値ノードリンクの作り方
// シングル数値ノードリンククラス
class ListNode {
val: number;
next: ListNode | null;
constructor(_val?: number, _next?: ListNode | null) {
this.val = _val === undefined ? 0 : _val;
this.next = _next === undefined ? null : _next;
}
}
// 配列からノードリンクを作成する
function createListNodeFromArray(l: number[]): ListNode | null {
if (l.length === 0) return null;
const base = new ListNode(l[0]);
// 先頭要素をノードの1つ目として指定
let currNode = base;
// 2つ目以降の要素でループ
for (let i = 1; i < l.length; i++) {
// まずはnextプロパティに現ループの要素ノードを設定
currNode.next = new ListNode(l[i]);
// ループ用のカレントノードを現ループの要素ノードにする
currNode = currNode.next;
}
return base;
}
Add Two Numbersの解
const l1 = [2, 4, 3],
l2 = [5, 6, 9];
const tes1 = createListNodeFromArray(l1);
const tes2 = createListNodeFromArray(l2);
const result = addTwoNumbers(tes1, tes2);
console.log({ result });
function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
// dummyは戻り値用。実際に戻り値となるリストノード自体はtempで作成する
// ただしtempはどんどんnextにシフトするため、実際に返す際には最深部のノードになっている。
// そのため、戻り値として使うのはdummy（dummyは先頭のノードを保持しているため）
let dummy = new ListNode(0);
let temp = dummy;
let carry = 0; // 繰り上がり
while (l1 !== null || l2 !== null || carry !== 0) {
let val1 = l1 ? l1.val : 0;
let val2 = l2 ? l2.val : 0;
let sum = val1 + val2 + carry;
// 合計値から繰り上がりの値を算出（0～9→0、10～19→1としたいので、十の位で切り捨て）
// 次のループの際に加算される
carry = Math.floor(sum / 10);
// 合計値から一の位の値を算出（0～9→0～9、10～19→0～9としたいので、10の余剰）
temp.next = new ListNode(sum % 10);
temp = temp.next;
if (l1 !== null) l1 = l1.next;
if (l2 !== null) l2 = l2.next;
}
// dummy自体のvalには不要な0が存在するため、dummy.nextを返す
// dummyを返す→[0,7,0,8], dummy.nextを返す→[7,0,8]
return dummy.next;
}
3. Longest Substring Without Repeating Characters
ポイント
- Mapを使い、文字と文字のインデックスを管理する
- スライディングウィンドウという、可変長の範囲（ウィンドウ）を動かすことで効率的に測定できる
const lengthOfLongestSubstring = function (_str: string) {
let length = 0;
const map = new Map();
// スライディングウィンドウでは、インデックスが囲む要素のウィンドウを追跡するために 2 つのインデックス (左と右) が必要なので、左インデックスを宣言します。
// スライディングウィンドウ：データ列に対して固定長または可変長のウィンドウを移動させながら処理を行うアルゴリズムや手法のこと。
let leftIdx = 0;
// ウィンドウを作成するため、常にライトインデックスはレフトインデックスよりも大きい必要がある
for (let rightIdx = 0; rightIdx < _str.length; rightIdx++) {
const char = _str[rightIdx];
// 文字が存在し、かつ、その存在した文字のインデックスが、レフトインデックスより大きいか確認。
// map.has(char)だけだと、"abba"のような文字列が対象の場合、
// "4文字目のa"のループの際に、本当はleftIndexを「4」としたいところ、
// "1文字目のa"のせいで「1」になってしまう。
// そこで、文字の位置がleftIndex以上の文字のみという条件を追加。
if (map.has(char) && map.get(char) >= leftIdx) {
// レフトインデックスの値を、対象の文字列のライトインデックス+1で上書き
// レフトインデックスは重複しない文字列長のスタート部分なので、
// 重複文字が存在したら、そこらから再スタートする
leftIdx = map.get(char) + 1;
}
// 前回ループと今回ループのウィンドウ長のどちらが大きいかをここで決定する。
// 結果の長さをその数値に設定します。
// ウィンドウ内のすべての要素を考慮する必要があるため、1を加算します
// （2 - 0 = 2ですが、要素は3つあるため1を加算します）。
length = Math.max(length, rightIdx - leftIdx + 1);
// キー(文字)が存在すれば新しいライトインデックスで上書き、なければ文字を追加
map.set(char, rightIdx);
}
return length;
};
Discussion