难度: Medium
Submission
运行时间: 226 ms
内存: 28.7 MB
class Solution:
def fixedRatio(self, s: str, num1: int, num2: int) -> int:
agg = 0
cnt = collections.defaultdict(int)
cnt[0] = 1
ans = 0
for c in s:
if c == "0":
agg -= num2
else:
agg += num1
ans += cnt[agg]
cnt[agg] += 1
return ans
Explain
此题解采用前缀和加哈希表的方法来解决问题。首先定义一个累加器agg，用于记录遍历字符串s时，基于字符'1'和'0'的加权累计值。权重由num1和num2确定，其中'1'对应num1，'0'对应-num2。使用哈希表cnt记录各个累计值出现的次数，其中cnt[0]初始化为1，代表累计值为0的初始状态。在遍历字符串的过程中，每读到一个字符就更新agg的值，并在哈希表中查找当前agg值的出现次数，这个次数直接加到最终的答案ans上，因为它表示以当前字符结尾的、符合固定比率的子字符串的数量。然后更新哈希表，将当前agg的计数增加1。这种方法通过在一次遍历中计算并累加符合条件的子字符串数量，避免了复杂的嵌套循环。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def fixedRatio(self, s: str, num1: int, num2: int) -> int:
agg = 0 # 初始化累加器
cnt = collections.defaultdict(int) # 哈希表记录每种agg值的出现次数
cnt[0] = 1 # 初始化，考虑累加值从0开始的情况
ans = 0 # 初始化答案
for c in s: # 遍历字符串中的每个字符
if c == '0':
agg -= num2 # 对于字符'0'，减去num2
else:
agg += num1 # 对于字符'1'，加上num1
ans += cnt[agg] # 累加当前agg值对应的前缀出现次数到答案中
cnt[agg] += 1 # 更新当前agg值的计数
return ans # 返回答案
Explore
在使用前缀和方法解题时，初始化`cnt[0]`为1是非常重要的一步。这是因为`cnt[0] = 1`代表了在任何字符被处理之前，累加器`agg`的值为0的一个有效状态。这允许算法正确地计算从字符串起始到当前位置的累加值正好为0的子字符串。例如，如果字符串的前几个字符累计值正好抵消为0，那么这些字符形成的子字符串就是一个有效的符合要求的字符串，它的存在需要通过`cnt[0]`来识别。简而言之，`cnt[0] = 1`确保了从字符串开头到当前位置的累加值为0的情况被正确计算。
当`num1`和`num2`的值非常大时，累加器`agg`的值变化幅度也会随之增大，这可以导致哈希表中存储的不同累加值数量显著增加。哈希表的大小直接依赖于这些不同累加值的数量。较大的`num1`和`num2`值可能使`agg`在每一步变化更大，从而产生更多独特的累加值。这种增加可能导致哈希表需要更多内存来存储这些值，并且在哈希表中查找、插入和更新操作的性能可能会随着哈希表大小的增加而降低，特别是如果哈希冲突增多时。因此，如果`num1`和`num2`非常大，可能需要优化哈希表的处理方式，例如通过使用更有效的哈希函数来减少冲突，或者考虑其他数据结构来优化性能。
此题的核心是使用累加器`agg`来维持字符'1'和'0'的固定比率。数学原理是通过前缀和的差来表示子字符串。每当`agg`通过添加`num1`或减去`num2`更新时，它实际上是在计算从字符串开始到当前字符的所有'1'和'0'的加权差。如果两个不同位置的前缀和相等，比如`agg[i]`和`agg[j]`，这意味着从位置`i+1`到`j`的子字符串中'1'和'0'的加权和为零，即`num1*count1 - num2*count0 = 0`，其中`count1`和`count0`分别是子字符串中'1'和'0'的数量。这可以被重新排列为`num1/num2 = count0/count1`，这正是我们要找的固定比率。因此，通过维护和比较`agg`的值，我们能够识别和计算符合特定比率的子字符串，这是通过巧妙地利用前缀和的性质和哈希表的快速查找能力实现的。