Arrays
Loading
Loading
Arrays
Precompute cumulative totals so any range answers in constant time.
By the end of this chapter
Store, for each position, the total of everything before it. Any range sum is then the difference of two entries.
nums = [3, 1, 4, 1, 5]prefix[0] = 0the empty prefixprefix[1] = 3sum of the first 1 elementprefix[3] = 8sum of the first 3 elementssum(1..3) = prefix[4] - prefix[1] = 9 - 3 = 61 + 4 + 1prefix = [0, 3, 4, 8, 9, 14]def build_prefix(nums): prefix = [0] * (len(nums) + 1) for i, value in enumerate(nums): prefix[i + 1] = prefix[i] + value return prefix def range_sum(prefix, i, j): """Inclusive sum of nums[i..j].""" return prefix[j + 1] - prefix[i]Rearranging the identity turns a search into a lookup. A range ending at j sums to the target exactly when some earlier running total equals runningTotal(j) - target.
def count_ranges(nums, target): seen = {0: 1} # the empty prefix has occurred once running = 0 count = 0 for value in nums: running += value count += seen.get(running - target, 0) seen[running] = seen.get(running, 0) + 1 return countCan you recognise the pattern?
A problem asks how many contiguous stretches have a particular sum, or repeatedly asks for the total over arbitrary ranges.
Quick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above, and try 3 practice problems.