Loading
Loading
Precompute cumulative totals so any range answers in constant time.
Build an array where each entry holds the total of everything before it. The sum of any range then becomes a single subtraction. Paired with a hash map of previously seen totals, the same idea answers questions about ranges with a particular sum without ever enumerating the ranges themselves.
`sum(i..j) = prefix[j + 1] - prefix[i]`. To count ranges with a target sum, rearrange it: for each endpoint j, the number of valid starts is how many times `prefix[j+1] - target` has already been seen.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def build_prefix(nums): """prefix[i] is the sum of nums[0:i], so prefix[0] == 0.""" 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] def count_subarrays_with_sum(nums, target): """Count ranges summing to target, in one pass.""" # The empty prefix has sum 0 and has been "seen" once. Without this, # subarrays starting at index 0 are never counted. seen = {0: 1} running = 0 count = 0 for value in nums: running += value count += seen.get(running - target, 0) seen[running] = seen.get(running, 0) + 1 return count| Status | Problem | Difficulty | Role |
|---|---|---|---|
| Running Altitude#1 | Easy | Primary | |
| Shelf Rebalance#2 | Easy | Primary | |
| Yield Without Self#5 | Medium | Primary | |
| Budget Windows#19 | Medium | Primary | |
| Reading Range Totals#148 | Easy | Primary | |
| Divisible Stretches#149 | Medium | Primary | |
| Plots With a Target Yield#150 | Hard | Primary |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in