リンク

質問リンク

問題の説明

開発者出身で世界一の金持ちになったApacheは、ストレスを解消するために実店舗で買い物をすることが多い.
魚桃は買い物をするとき、売り場の棚の特定の範囲のものを一掃することに慣れています.
ある日、ストレスを解消するためにジュエリーショップに買い物に行ったフィッチは、以前のように棚のすべての特定の範囲のジュエリーを購入し、特に以下の目的を達成したいと思っていました.
少なくとも1つ以上陳列されている宝石を含む最短区間を探して購入します.
例えば、以下に、8種類の宝石(RUBY、DIA、EMERALD、SAPPHIRE)を示す例を示す.

棚の3番から7番まで5つの宝石を購入し、すべての種類の宝石は少なくとも1つ以上含まれています.
棚の3、4、6、7番の宝石だけを購入すると、真ん中に特定の区間(5番)が欠け、魚の皮魚の買い物習慣に合わない.
パラメータは、ショーケース番号順に宝石名を格納する配列gemsです.この場合、1つ以上の宝石を含む最短区間を見つけて戻ります.
最短区間の開始棚番号と終了棚番号を順番にシーケンスに入れて返し、複数の最短区間がある場合は開始棚番号の最小区間を返します.

せいげんじょうけん

gemsアレイのサイズは100000を超えません.

gems配列の各要素は、棚にリストされている宝石を表します.

gemsの配列では,1番棚から宝石名を棚番号順に格納する.

gems配列の各要素は1つの文字列であり、長さが1または10未満のアルファベット大文字のみから構成されています.

I/O例

I/O例説明

I/O例#1
問題の例を以下に示します.
I/O例#2
3種類の宝石(AA,AB,AC)を含む最短区間は[1,3],[2,4]である.
開始棚番号は、より小さな[1,3]を返さなければなりません.
I/O例#3
1種の宝石(XYZ)を含む最短領域は[1,1],[2,2]および[3,3]である.
開始棚番号は最小[1,1]を返さなければなりません.
I/O例#4
全4種の宝石(ZZZ,YY,NNN,BBB)を含む領域は[1,5]のみである.
したがって、[1,5]に戻る必要があります.

に答える

gemsアレイに何種類の宝石があるか(jmap.size()

ダブルポインタアルゴリズムに基づいて、宝石が詰められる前に++を終了します.

endが停止すると、今度は宝石が詰まらないまで++を開始します.

海図として値を記録し続けます.

番と3番の繰り返し文が終わるたびにend-startが最も時間がかかります.

nが1以上100000以下である場合,さらに効率テストがあり,O(n)で終わるような情報である.
そのため、二重ポインタ技術は自然に現れた.
解决して后悔したら、必ずスケジュールを书いてください.

コード#コード#

import java.util.*; class Solution { public int[] solution(String[] gems) { int[] answer = new int[2]; int jewel, i; Map<String, Integer> jmap = new HashMap<>(); for(i = 0; i < gems.length; i++) { if(jmap.get(gems[i]) == null) jmap.put(gems[i], 1); } jewel = jmap.size(); Map<String, Integer> apmap = new HashMap<>(); int start = 0; int end = 0; int now = 0; int sub = 1000001; while(end < gems.length) { for(; end < gems.length && now < jewel; end++) { apmap.put(gems[end], apmap.getOrDefault(gems[end], 0) + 1); if(apmap.get(gems[end]) == 1) now++; } for(; start < end && now == jewel; start++) { apmap.put(gems[start], apmap.get(gems[start]) - 1); if(apmap.get(gems[start]) == 0) now--; } if(sub > end - start) { answer[0] = start; answer[1] = end; sub = end - start; } } return answer; } }