Prefix Sum

• Prefix[i] will have value calculated till ith index.

Subarray sum equals k

res = 0
presumToCount = defaultdict(int)
presum = 0
for num in nums:
    presum += num
    if presum == k:
        res += 1
    res += presumToCount[presum - k]
    presumToCount[presum] += 1
return res

Problems

• 2845. Count of Interesting Subarrays
• 1915. Number of Wonderful Substrings
  • Similar to sub array sum equals k, but we use bitmask and xor operations on the prefix values to find the substrings with zero odd count (prefix is zero) and with 1 odd count.