Subarray Sum Equals K

1. The obvious way

   Try every start and end: O(n²).

2. The key insight

   Keep the running total and a notebook counting how many times each running total has occurred. At each step the number of ranges ending here with sum k = how many earlier totals equal (current total - k). Start the notebook with total 0 seen once, so ranges that begin at the very start count too.

3. The algorithm
   1. Notebook: total 0 has been seen once. Running total = 0, answer = 0.
   2. Add the next number to the running total.
   3. Look up (running total - k) in the notebook; add that count to the answer.
   4. Write the running total in the notebook (count + 1) and continue.

Watch it run

totals seen: {0: 1}   answer 0

def subarray_sum(nums, k):
    seen = {0: 1}                      # running total -> how many times
    running = 0
    answer = 0
    for number in nums:
        running += number
        answer += seen.get(running - k, 0)     # ranges ending here with sum k
        seen[running] = seen.get(running, 0) + 1
    return answer

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.