---
# System prepended metadata

title: 2489. Number of Substrings With Fixed Ratio
tags: [Leetcode, Prefix Sum, Medium, Math]

---

# 2489. Number of Substrings With Fixed Ratio
###### tags: `Leetcode` `Medium` `Math` `Prefix Sum`
Link: https://leetcode.com/problems/number-of-substrings-with-fixed-ratio/description/
## 思路
prefix sum的思想
我们希望找到一个prev位置 使得
```
(curr1-prev1)/(curr0-prev0) = num2/num1
num2*curr0 - num2*prev0 = num1*curr1 - num1*prev1
num2*curr0 - num1*curr1 = num2*prev0 - num1*prev1
```
```curr0```, ```curr1```是当前0和1的prefix数目
所以这里我们需要计算的prefix其实是```num2*curr0-num1*curr1```
## Code
```python=
class Solution:
    def fixedRatio(self, s: str, num1: int, num2: int) -> int:
        ans = prefix = 0
        freq = Counter({0:1})
        for ch in s:
            if ch=='0':
                prefix += num2
            else: prefix -= num1
            ans += freq[prefix]
            freq[prefix] += 1
        return ans
```