シラバス レッスン 148 中 55 · キャッシュなしの速さ
キャッシュなしの速さ

2 つのポインタ、表なし

なぜ大切か 「足すと X になる 2 つのものを見つける」には有名な答えがあります。すべてを集合に入れ、相手を調べるのです。速く、そしてすべてのデータの写しが要ります。データが並べられているなら、メモリはほとんど要りません。

贈り物のサービスが、違う 2 つの商品のセットを決まったセット価格で売ります。商品の価格の一覧は並べられていて、重複がなく、空きメモリのとても少ない組み込みの端末にあります。あるセット価格について、価格を足すとちょうどその価格になる商品の組の数が必要です。

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
あなたの番

count_pairs(tape, target) を書いてください。tape は昇順に並べた、重複のない整数の価格の Tape です。足すとちょうど target になる違う 2 つの項目の組がいくつあるかを返します(それぞれの組は一度だけ数える)。予算:20,000 の項目で読むのは最大 60,000 の値、関数が動く間の作業用のメモリは最大 16,000 バイト(tracemalloc で測る。20,000 の価格の集合やリストは 150,000 バイトを超えます)。len(tape) は無料です。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。