Data Structures19 sections · 729 units
Open in Course

The Core Idea

Counting complements

If prefix[j]prefix[i]=kprefix[j] - prefix[i] = k, then the subarray from i+1i+1 to jj has sum kk. Rearranging: prefix[i]=prefix[j]kprefix[i] = prefix[j] - k.

For each jj, count how many i<ji < j have prefix[i]=prefix[j]kprefix[i] = prefix[j] - k. That's how many subarrays ending at jj have sum kk.

Use a hash map to count occurrences of each prefix sum. For each new prefix sum, look up how many times (currentk)(current - k) has appeared.