---
# System prepended metadata

title: 2845. Count of Interesting Subarrays
tags: [Leetcode, HashMap, Prefix Sum, Medium]

---

Link: https://leetcode.com/problems/count-of-interesting-subarrays/description/
## 思路
We don't care about the value of ```num``` in ```nums```, what we care is whether ```num%modulo==k```
We subsitite ```num``` who satisfies ```num%modulo==k``` with 1, otherwise 0, and we compute the prefix sum
If the current prefix sum is ```currPrefixCnt```, and we want to get how many subarrays ending with current number has cnt which ```cnt%modulo==k```, we just need to find out how many positions before this position have prefixCnt that ```(currPrefixCnt-prefixCnt)%modulo==k```
## Code
```python=
class Solution:
    def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
        ans = prefixCnt = 0
        count = collections.defaultdict(int)
        count[0] = 1
        for num in nums:
            prefixCnt += 1 if num%modulo == k else 0
            prefixCnt %= modulo
            ans += count[(prefixCnt-k+modulo)%modulo]
            count[prefixCnt] += 1
        return ans
```