「1回の走査で行う」という面接の質問のほとんどは、答えが同じです:見たものを、1ステップで調べられる何かをキーにして、辞書か集合に覚えておくことです。
- 見たものの集合:最初の繰り返し、重複、「このIDに前に会ったか?」です。
- 補数の参照:足して目標になる2つの値には、各値の位置を保存し、新しい値ごとに
target - valueを調べます。
- グループ化のキー:アナグラムを並べ替えた文字の下にまとめるように、一緒になるべき項目を同じキーの下に置きます。
- 件数:
Counterは、2回の走査で「1回だけ出てくる最初の項目」に答えます。
- すべての値の集合:連続をその最初の値(
x - 1が集合にない)からだけ始められるので、連続する数の最も長い連続がO(n)で求まります。
スキルは、キーを選ぶことです。次の項目が届いたときに、すぐに何を見つける必要があるかを考えてください。