Præfiksummer og løbende totaler
Opbyg præfikssum-arrays for at besvare intervalsum-forespørgsler i O(1), og anvend teknikken på subarray-problemer som subarray med maksimal sum.
Præfiksummer og løbende totaler er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 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 intervalsummer
Givet et array nums skal du besvare mange forespørgsler af formen: hvad er summen af elementerne fra indeks i til indeks j? Hvis hver forespørgsel beregnes naivt, tager det O(n) tid, så k forespørgsler koster O(n×k). Med et præfikssumsarray forudberegner du en løbende total på O(n) tid og kan derefter besvare hver forespørgsel på O(1) tid. Dette er en af de mest anvendte forudberegningsteknikker ved jobsamtaler.
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operationsOpbygning af præfikssumsarrayet
Definér prefix[i] som summen af nums[0] til og med nums[i-1] (én ekstra plads; et nulindekseret forskydning på 1 gør grænsetilfælde enklere). Opbyg det på O(n) tid med én gennemgang: prefix[i] = prefix[i-1] + nums[i-1]. Derefter bliver en intervalforespørgsel sum(i, j) til prefix[j+1] - prefix[i]: én subtraktion, der koster O(1).
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15Delarraysum lig med K
At finde antallet af delarrays med en sum lig med k er et klassisk problem med hashmap og præfikssum. Den afgørende indsigt er, at delarraysummen fra i til j er lig med prefix[j] - prefix[i-1]. Hvis denne skal være lig med k, gælder prefix[i-1] = prefix[j] - k. Mens du gennemgår arrayet fra venstre mod højre og vedligeholder en løbende præfikssum, slår du op, hvor mange gange current_sum - k er forekommet tidligere, og tæller dermed alle gyldige delarrays på O(n) tid i alt.
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])Maksimal delarraysum med præfiks
Den maksimale delarraysum kan formuleres som et præfikssumproblem: for hvert indeks j vil vi maksimere prefix[j] - prefix[i] for alle i < j. Det optimale i ved hvert j er den mindste præfikssum, der er set indtil videre. En gennemgang fra venstre mod højre, hvor du holder styr på min_prefix, giver O(n) tid. Det svarer til Kadane-algoritmen set gennem præfikssummernes perspektiv.
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -12D-præfikssummer til gitterforespørgsler
Præfikssummer kan også bruges på 2D-gitre. Definér P[i][j] som summen af alle elementer i rektanglet fra (0,0) til (i-1,j-1). Opbyg det med inklusions-eksklusionsformlen: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Derefter kan enhver forespørgsel efter summen af rektanglet fra (r1,c1) til (r2,c2) besvares på O(1) tid ved hjælp af fire opslag.
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14Løbende total for ligevægtsindeks
Ligevægtsindekset er den position, hvor summen af elementerne til venstre er lig med summen til højre. Forudberegn den samlede sum, og gennemgå derefter arrayet, mens du vedligeholder en løbende venstresum. Højresummen er total - left_sum - nums[i]. Kontrollér ligheden på O(1) tid pr. indeks, hvilket giver O(n) tid i alt. Det viser, hvordan en løbende total kan erstatte to separate præfikssumsarrays.
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1Produkt af arrayet uden elementet selv
Givet et array skal du returnere et array, hvor hvert element er produktet af alle de øvrige elementer. Division er ikke tilladt. Brug et præfiksprodukt og et suffiksprodukt: result[i] = (produktet af alle elementer før i) × (produktet af alle elementer efter i). Opbyg præfiksprodukterne i en gennemgang fra venstre mod højre, og gang derefter suffiksprodukterne på i en gennemgang fra højre mod venstre ved hjælp af en løbende variabel — der kræves ikke noget ekstra array til suffikset.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra spacePræfikssum med modulo
Nogle problemer spørger efter antallet af delarrays, hvis sum er delelig med k. Ved at bruge præfikssummer modulo k gælder det, at hvis prefix[j] % k == prefix[i] % k, så er sum(i+1..j) delelig med k. Et hashmap, der tæller hver restværdi, mens vi gennemgår arrayet, giver O(n) tid. Den afgørende initialisering er freq[0] = 1, så delarrays, der begynder ved indeks 0, håndteres korrekt.
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)Differensarray til intervalopdateringer
Et differensarray er det omvendte af en præfikssum. Givet et array forudberegner du diff[i] = nums[i] - nums[i-1]. Hvis du vil lægge x til et interval [l, r], kræver det kun to O(1)-operationer på differensarrayet: diff[l] += x og diff[r+1] -= x. Efter alle opdateringer genopbygger du resultatarrayet med én præfikssumsgennemgang. Det ændrer k intervalopdateringer fra O(n×k) til O(n + k).
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]Præfikssum i opgaver ved jobsamtaler
Præfikssummer optræder i mange problemkategorier:
- Intervalforespørgsler — delarraysum, rektangelsum
- Optælling af delarrays — sum lig med k, delelig med k
- Produktproblemer — produkt uden elementet selv
- Ligevægt — find pivotindeks
- Intervalopdateringer — differensarray
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3Løbende sum og løbende maksimum
Ud over præfikssummer bruger mange problemer et løbende maksimum eller et løbende minimum, der vedligeholdes med én variabel. Problemet med at købe aktier på det bedste tidspunkt bruger den løbende minimumspris; problemet med at opsamle regnvand fra venstre bruger den løbende maksimale højde fra venstre. Disse mønstre kræver kun én gennemgang og O(1) ekstra plads, hvilket gør dem til guldstandarden for både tids- og pladseffektivitet.
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5Hurtigt tjek
Test din forståelse af begreberne fra lektionen i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du, at præfikssummer omdanner O(n)-forespørgsler på intervaller til opslag på O(1) tid ved at forudberegne kumulative summer i én O(n)-gennemgang, at kombinationen af præfikssummer og et hashmap muliggør O(n)-løsninger til optælling af delarrays med en given sum eller delelighedsegenskab, og at differensarrays er det omvendte: de tillader O(1)-intervalopdateringer med én præfikssumsgennemgang til genopbygning i slutningen. Dernæst tager vi fat på to-pointer-teknikken, begyndende med pointere i hver sin ende.
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 “Præfiksummer og løbende totaler” gratis?
Ja — hele teksten til “Præfiksummer og løbende totaler” 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 “Præfiksummer og løbende totaler”?
Opbyg præfikssum-arrays for at besvare intervalsum-forespørgsler i O(1), og anvend teknikken på subarray-problemer som subarray med maksimal sum. 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 2 af 4.
Hvor lang tid tager lektionen “Præfiksummer og løbende totaler”?
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
- Grundlæggende arrays og in-place-operationer
- Præfiksummer og løbende totaler
- To pointers: modsatte ender
- To pointers: langsom og hurtig