Räkna delarrayer med en målsumma

Nu kommer twisten: räkna hur många delarrayer som har summan k. Att kontrollera varje par är långsamt, men prefixsummor tillsammans med en hash map löser det. 🎯

Summan av en delarray är prefix[r + 1] minus prefix[l]. En summa på k innebär alltså att två prefixvärden skiljer sig exakt med k.

Om det aktuella prefixet är P behöver Ni ett tidigare prefix som är lika med P minus k. Den här omformningen är hela tricket.

I stället för att gå bakåt vid varje steg håller Ni reda på hur ofta varje prefixvärde har förekommit. En löpande räkning ger svaret i O(1).

En dictionary mappar varje prefixvärde till hur många gånger Ni har sett det. Den här kartan gör uppslagningen till en omedelbar räkning.

Innan loopen registrerar Ni att prefix 0 har förekommit en gång. Den här initieringen gör att delarrayer som börjar vid index 0 räknas med.

För varje element uppdaterar Ni det löpande prefixet, lägger till antalet förekomster av det nödvändiga värdet och registrerar sedan det aktuella prefixet. Ett enda pass gör allt.

Ni måste lägga till i svaret innan Ni registrerar det aktuella prefixet. Annars smyger ett intervall med längden noll in och räkningen blir fel.

Varje element kräver konstant arbete, så hela räkningen körs i O(n). Det slår den brutala O(n²)-lösningen på stora indata.

Till skillnad från glidande fönster hanterar den här metoden negativa tal utan problem, eftersom prefixskillnaderna förblir giltiga oavsett tecken.

Det här mönstret löser det berömda problemet med delarray-summa lika med k och många förklädda varianter i tävlingsdomare.

Ni kan räkna delarrayer med målsumman i O(n) med hjälp av prefixsummor och en frekvenskarta. Initiera prefix 0 och räkna sedan innan Ni registrerar. ✅