Kurrikulum Leson 55 van 148 · Spoed sonder die cache
Spoed sonder die cache

Twee wysers, geen tabel nie

Waarom dit saak maak "Vind twee dinge wat bymekaar optel tot X" het 'n bekende antwoord: sit alles in 'n set en soek die maat op. Dit is vinnig, en dit het 'n kopie van al die data nodig. Wanneer die data gesorteer is, het jy byna geen geheue nodig nie.

A geskenkdienste verkoop pakkette van twee verskillende produkte teen 'n vaste pakketprys. Die produkpryslys is gesorteer, het geen herhalings nie, en sit op 'n ingebed toestel met baie min vrye geheue. Vir 'n pakketprys het jy die aantal produkpaare nodig waarvan die pryse presies bymekaar optel tot daardie prys.

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
Jou beurt

Skryf count_pairs(tape, target). tape is 'n Tape van heelgetalpryse, gesorteer op stygende volgorde, sonder herhalings. Gee terug hoeveel pare van twee verskillende items presies byeenkom tot target (elke paar word een keer getel). Budgets: vir 20,000 items wat hoogstens 60,000 waardes lees, en gebruik hoogstens 16,000 bytes van werksgeheue terwyl jou funksie loop (gemeet met tracemalloc; 'n set of lys van die 20,000 pryse is meer as 150,000 bytes). len(tape) is gratis.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.