# 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 ```