Byg et præfiksum-array
Forberegn løbende totaler én gang
Byg et præfiksum-array er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Problemet med gentagne summer
Forestil dig, at du skal besvare hundredvis af forespørgsler om intervalsummer i ét array. Det er langsomt at summere hvert interval fra bunden. En præfikssum løser problemet. 🚀
Hvad en præfikssum er
Et array med præfikssummer gemmer summen af alle elementer frem til hvert indeks. Ét forudberegnende gennemløb gør langsomme summeringer til øjeblikkelige svar.
Et lille eksempel
For [3, 1, 4] er de løbende summer 3, derefter 4 og til sidst 8. Denne voksende liste med summer er præcis din præfikssum.
Den centrale rekurrens
Hver indgang er den forrige sum plus det aktuelle element. Denne korte rekurrens er kernen i hele teknikken.
prefix[i] = prefix[i - 1] + a[i]Implementér det i kode
Gå gennem arrayet én gang, mens du holder styr på en løbende sum. Ved hvert trin tilføjer du den nye sum, så arrayet bygges i ét lineært gennemløb.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Hvorfor et indledende nul hjælper
Hvis du starter prefix med et indledende nul, indeholder prefix[i] summen af de første i elementer. Det gør senere intervalberegninger enkle.
Indekseringskonvention
Med nullet forrest er prefix[k] lig med a[0] + ... + a[k-1]. Hvis du holder fast i denne konvention, undgår du smertefulde fejl med én forskydning.
Omkostninger ved opbygningen
Når du bygger præfikssumsarrayet, berører du hvert element præcis én gang, så det koster O(n) tid. Du betaler denne pris én gang og kan derefter genbruge resultatet.
Forberegn én gang, forespørg ofte
Den store gevinst er afvejningen: Brug ét lineært gennemløb på forhånd, så hver senere forespørgsel om en sum bliver et hurtigt opslag i stedet for en løkke.
En genvej i Python
Standardbiblioteket kan beregne summerne for dig. itertools.accumulate producerer de løbende summer i ét enkelt kald.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Hold øje med hukommelsen
Præfikssumsarrayet har samme længde som dine inddata plus én. Ved meget store inddata skal du huske, at det fordobler dit hukommelsesforbrug.
Hurtig kontrol
Du bygger et præfikssumsarray. Hvad indeholder indeks 0 normalt?
Opsamling
Du har lært at bygge et array med præfikssummer i ét O(n)-gennemløb med et indledende nul for enkel indeksering. Forberegn én gang, og genbrug derefter resultatet. ✅
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Byg et præfiksum-array” gratis?
Ja — hele teksten til “Byg et præfiksum-array” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Byg et præfiksum-array”?
Forberegn løbende totaler én gang Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Byg et præfiksum-array”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Byg et præfiksum-array
- Summér ethvert interval med subtraktion
- Tæl subarrays med en målsum
- Differensarrays til intervalopdateringer