[プログラマー]ジュエリーショッピング(Python)

ダブルポインタで解決すべきだと思いますが、アイデアが思いつかないので、他の人の問題を解くを参考にしました.文章の核心について以下のように理解した.

区間[a,b]からすべての種類の宝石が買えるようになったことからa+=1となる.△i.e.区間の範囲が縮小した。そしてすべての範囲の宝石が買えるかどうか見てみましょう。買えるものは買えないまで縮小する。逆に、絞り込んだ区間で全ての種類の宝石が買えない場合は、b+=1として区間の範囲を広げ、全ての種類の宝石が買えるかを確認します。この手順を、aがnまたはbがnになるまで繰り返します。(nは宝石数)

上記の過程で得られた区間のうち、最小区間を求めればよい.アイデアに基づいて実現すると、中に歪みが現れ、あるTCでa>b (아래의 코드에서는 lp > rp)のとき.(e.g.24579142)正解は得られましたが、私のコードではなく上のリンクを参照することをお勧めします.

1.コード

from collections import defaultdict

def solution(gems):
    size = len(gems)
    kinds = len(set(gems))
    d = defaultdict(int)
    lp, rp = 0, 0
    answer = [0, int(1e9)]
    count = 0
    has_all_kind = False

    while lp < size and rp < size:
        if not has_all_kind:
            if not d[gems[rp]]: count += 1
            d[gems[rp]] += 1
        
        if count == kinds:
            d[gems[lp]] -= 1
            if not d[gems[lp]]: count -= 1           
            answer = min(answer, [lp+1, rp+1], key=lambda x: abs(x[0]-x[1]))
            lp += 1
            has_all_kind = True
            continue
            
        has_all_kind = False
        rp += 1
            
    return answer