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)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.
Hierdie blutser blokkeer koekies vir learn.floati.life, so lesse wat jy hier voltooi het kan nie in volgorde oopgaan nie. Laat koekies vir hierdie webwerf toe en laai nuut.