Arrays & Hashing

class Solution {
    // 例: nums = [1, 2, 3, 3]  ->  true
    hasDuplicate(nums: number[]): boolean {
        const seen = new Set<number>();
        // ループを1度回すだけ
        for (const num of nums) {
            if (seen.has(num)) return true;
            seen.add(num);
        }
        return false;
    }
}

class Solution {
    // 例: s = "racecar", t = "carrace"  ->  true
    isAnagram(s: string, t: string): boolean {
        // 長さが違えば個数が一致しようがない
        if (s.length !== t.length) return false;

        const A = 'a'.charCodeAt(0);
        // アルファベットの文字数
        const freq = new Array(26).fill(0);

        for (let i = 0; i < s.length; i++) {
            freq[s.charCodeAt(i) - A]++; // s に出た分を足す
            freq[t.charCodeAt(i) - A]--; // t に出た分を引く
        }

        // 打ち消し合って全部 0 なら、内訳が完全に一致している
        return freq.every((n) => n === 0);
    }
}

class Solution {
    // 例: nums = [3, 4, 5, 6], target = 7  ->  [0, 1]
    twoSum(nums: number[], target: number): number[] {
        // 値 -> その値があった添字（index）
        const seen = new Map<number, number>();

        for (let i = 0; i < nums.length; i++) {
            const diff = target - nums[i];

            if (seen.has(diff)) return [seen.get(diff)!, i];

            seen.set(nums[i], i);
        }

        return [];
    }
}

class Solution {
    // 例: strs = ["act", "pots", "cat", "stop"]  ->  [["act", "cat"], ["pots", "stop"]]
    groupAnagrams(strs: string[]): string[][] {
        // ソート済みの文字列 -> そこに属する元の文字列たち
        const groups = new Map<string, string[]>();

        for (const str of strs) {
            const key = str.split('').sort().join('');
            const group = groups.get(key) ?? [];

            group.push(str);
            groups.set(key, group);
        }

        return [...groups.values()];
    }
}

class Solution {
    // 例: nums = [1, 1, 1, 2, 2, 3], k = 2  ->  答えは [1, 2]
    topKFrequent(nums: number[], k: number): number[] {
        // ① 数える。Map は「キー -> 値」の対応表
        const count = new Map<number, number>();
        for (const num of nums) {
            // まだ一度も出ていなければ get は undefined を返すので、?? 0 で 0 とみなす
            count.set(num, (count.get(num) ?? 0) + 1);
        }
        // count = { 1 => 3, 2 => 2, 3 => 1 }  （1 が3回、2 が2回、3 が1回）

        // ② 並べ替えて頭から k 個
        return [...count] // Map を配列に開く -> [[1, 3], [2, 2], [3, 1]]
            .sort((a, b) => b[1] - a[1]) // [1] は「回数」。b - a なので降順（多い順）
            //                              ここだけ O(n log n)。1行に見えるが
            //                              中で「2つを比べる」を n log n 回まわしている
            .slice(0, k) // 先頭 k 組だけ -> [[1, 3], [2, 2]]
            .map(([num]) => num); // 各組から値だけ取り出す -> [1, 2]
    }
}

class Solution {
    // 例: nums = [1, 1, 1, 2, 2, 3], k = 2  ->  答えは [1, 2]
    topKFrequent(nums: number[], k: number): number[] {
        // ① 数える（ここはソート版と同じ）… n 回
        const count = new Map<number, number>();
        for (const num of nums) {
            count.set(num, (count.get(num) ?? 0) + 1);
        }
        // count = { 1 => 3, 2 => 2, 3 => 1 }

        // ②-a 「回数 f の値を入れるバケツ」を byFreq[f] として用意する … n 回
        //      回数は最大でも n（全部同じ値のとき）なので、添字 n が使えるよう n+1 本作る
        const byFreq: number[][] = Array.from({ length: nums.length + 1 }, () => []);
        for (const [num, freq] of count) {
            byFreq[freq].push(num); // 「3回出た値は 1」なら byFreq[3] に 1 を入れる
        }
        // count のキーと値が入れ替わった形になる:
        // byFreq = [ [], [3], [2], [1], [], [], [] ]
        //    添字     0    1    2    3   4   5   6
        //                  ↑    ↑    ↑
        //             1回出た 2回出た 3回出た値

        // ②-b 添字の大きい側（＝回数が多い側）から、k 個そろうまで拾う … 多くても n 回
        //      「比べる」作業がどこにもないのがポイント。置いた場所がそのまま順位になっている
        const top: number[] = [];
        for (let freq = nums.length; freq > 0 && top.length < k; freq--) {
            top.push(...byFreq[freq]); // バケツの中身をまとめて足す（空なら何も起きない）
        }
        // freq = 6,5,4 は空 -> freq = 3 で 1 を追加 -> freq = 2 で 2 を追加 -> 2個そろって終了

        // 同じ回数の値が複数あると k を超えて入ることがあるので、最後に切りそろえる
        return top.slice(0, k); // [1, 2]
    }
}

class Solution {
    // 例: strs = ["ab", "c:d"]  ->  "2:ab3:c:d"
    encode(strs: string[]): string {
        // 「長さ:本体」を並べる。長さがあるので、本体に : が入っていても壊れない
        return strs.map((s) => `${s.length}:${s}`).join('');
        //   "2:ab"        +      "3:c:d"
    }

    // 例: "2:ab3:c:d"  ->  ["ab", "c:d"]
    decode(str: string): string[] {
        //  "2:ab3:c:d"
        //   012345678   <- 添字。本体の : は添字 7 にいる
        const res: string[] = [];
        let i = 0;

        // i は文字列の長さぶん飛ばしていくので for にはしない
        while (i < str.length) {
            const colon = str.indexOf(':', i); // i 以降で最初の : の位置
            const length = Number(str.slice(i, colon));
            const start = colon + 1; // : の次が本体の先頭

            res.push(str.slice(start, start + length));
            i = start + length; // 次の「長さ」の先頭へ
        }
        // 1周目: i=0  colon=1  length=2  start=2  ->  slice(2, 4) = "ab"   ->  i=4
        // 2周目: i=4  colon=5  length=3  start=6  ->  slice(6, 9) = "c:d"  ->  i=9 で終了
        //        添字 7 の : は 2周目の slice が丸ごと持っていくだけ。
        //        indexOf が i=4 から探すと、先に見つかるのは添字 5 の : のほう

        return res;
    }
}

class Solution {
    // 例: nums = [1, 2, 3, 4]  ->  [24, 12, 8, 6]
    productExceptSelf(nums: number[]): number[] {
        const n = nums.length;
        // 長さ n だけ確保した空の箱。中身は ① で全部埋めるので fill は要らない
        const res = new Array<number>(n);

        // ① 左から: res[i] に「自分より左の積」を置く
        let prefix = 1;
        for (let i = 0; i < n; i++) {
            res[i] = prefix; // 置く時点の prefix に自分はまだ入っていない
            prefix *= nums[i]; // 置いたあとで自分を混ぜる
        }
        // res = [1, 1, 2, 6]  （1, 1, 1×2, 1×2×3）

        // ② 右から: そこに「自分より右の積」を掛ける。①の鏡写し
        let suffix = 1;
        for (let i = n - 1; i >= 0; i--) {
            res[i] *= suffix;
            suffix *= nums[i];
        }
        // res = [1×24, 1×12, 2×4, 6×1] = [24, 12, 8, 6]

        return res;
    }
}

class Solution {
    // 例: nums = [2, 20, 4, 10, 3, 4, 5]  ->  4
    longestConsecutive(nums: number[]): number {
        // 重複が消え、「この値はあるか」が O(1) で聞けるようになる
        const numSet = new Set(nums);
        // 空配列ならこのまま 0 が返る。特別扱いが要らない
        let longest = 0;

        for (const num of numSet) {
            // 1つ前があるなら自分は列の途中。数えるのは先頭の担当なので飛ばす
            if (numSet.has(num - 1)) continue;

            let length = 1;
            while (numSet.has(num + length)) length++;

            longest = Math.max(longest, length);
        }

        return longest;
    }
}