[JS]プログラマーの宝石購入

質問リンク

https://programmers.co.kr/learn/courses/30/lessons/67258

中学3年生

まず無知な...
最初のインデックスから,満たされた区間内で最短区間を求める.
2中for Moonなので、タイムアウトは間違いないと知っていましたが...むなしい

function solution(gems) {
    var answer = [];
    const db = new Set(gems);
    if (db.size === 1) return [1, 1]

    gems.forEach((gem, idx) => {
        const visit = {};
        [...db].forEach(el => visit[el] = 1);
        visit[gem] = 0;

        var targetLen = db.size - 1, nextIdx = idx;
        for (; nextIdx < gems.length; nextIdx++) {
            const target = gems[nextIdx];
            if (visit[target]) {
                targetLen--;
                if (targetLen === 0) break;

                visit[target] = 0;
            }
        }
        if (!targetLen) answer.push([idx + 1, nextIdx + 1]);
    })
    return answer.reduce((ac, v) =>
        ac[1] - ac[0] > v[1] - v[0] ? v : ac, [1, gems.length]);
}

再解釈

スライドウィンドウアルゴリズム
理論上O(n)

ウィンドウを順次拡張します.
AA BB BB AA AA CC DD AA
AA: 1, BB: 2

繰り返しが発生すると、インデックスが加算されます.
AA BB BB AA AA CC DD AA
AA: 1, BB: 3

条件が満たされたら正解候補に変更する->正解と比較する
AA BB BB AA AA CC DD AA
AA: 5, BB: 3, CC: 6, DD: 7 -> [3, 7]
AA BB BB AA AA CC DD AA
AA: 8, BB: 3, CC: 6, DD: 7 -> [3, 8]

function solution(gems) {
    const cnt = new Set(gems).size;
    const gemMap = {};
    var answer = [1, gems.length];
    gems.forEach((gem, i) => {
        gemMap[gem] = i;
        const target = Object.values(gemMap);
        if (target.length === cnt) {
            const cand = [Math.min(...target) + 1, i + 1];
            answer = answer[1] - answer[0] > cand[1] - cand[0] ? cand : answer;
        }
    })
    return answer;
}

演算子を展開...和Math.min,Object.valuesで配列長を求める過程は想像以上に重いようだ.

最終コード

他の人と同じように...Mapオブジェクトを使用すると簡単にsizeを取得できます.
Mapは挿入順序を保持し,最小比較演算は不要である.

function solution(gems) {
    const cnt = new Set(gems).size;
    const gemMap = new Map();
    var answer = [1, gems.length];
    gems.forEach((gem, i) => {
        gemMap.delete(gem);
        gemMap.set(gem, i);
        if (gemMap.size === cnt){
            const cand = [gemMap.values().next().value + 1, i + 1];
            answer = answer[1] - answer[0] > cand[1] - cand[0] ? cand : answer;
        }
    })
    return answer;
}

私たちはMap.を使います.

コードの追加

公式の問題を参考にして説明し,書き直す
https://tech.kakao.com/2020/07/01/2020-internship-test/

これはより直感的なアルゴリズムのようだ.

右++(周波数+1)

Left++(周波数-1、周波数が0の場合はMapから削除)

right繰返し

function solution(gems) {
    const cnt = new Set(gems).size;
    var ans = [1, gems.length];

    var l = 0, r = 0;
    const hit = new Map();
    hit.set(gems[0], 1)

    while (r < gems.length) {
        if (hit.size === cnt) {
            if(ans[1] - ans[0] > r - l)
                ans = [l + 1, r + 1]

            hit.set(gems[l], hit.get(gems[l]) - 1);
            if (hit.get(gems[l]) === 0) 
                hit.delete(gems[l])

            l++;
        }
        else {
            r++;
            const right = hit.get(gems[r]);
            hit.set(gems[r], right ? right + 1 : 1);
        }
    }
    return ans;
}