固定比率的子字符串数
难度:
标签:
题目描述
代码结果
运行时间: 226 ms, 内存: 28.7 MB
/*
* Leetcode 2489: 固定比率的子字符串数
* 题目思路:
* 1. 使用Stream API进行字符统计。
* 2. 利用滑动窗口的方式遍历字符串并检查比率。
* 3. 当满足比率条件时,更新结果计数。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public int fixedRatioSubstring(String s, int a, int b) {
int[] result = {0};
IntStream.range(0, s.length()).forEach(i -> {
int[] charCount = new int[2]; // [0] for 'a', [1] for 'b'
IntStream.range(i, s.length()).forEach(j -> {
if (s.charAt(j) == 'a') charCount[0]++;
if (s.charAt(j) == 'b') charCount[1]++;
if (charCount[0] * b == charCount[1] * a) result[0]++;
});
});
return result[0];
}
}
解释
方法:
此题解采用前缀和加哈希表的方法来解决问题。首先定义一个累加器agg,用于记录遍历字符串s时,基于字符'1'和'0'的加权累计值。权重由num1和num2确定,其中'1'对应num1,'0'对应-num2。使用哈希表cnt记录各个累计值出现的次数,其中cnt[0]初始化为1,代表累计值为0的初始状态。在遍历字符串的过程中,每读到一个字符就更新agg的值,并在哈希表中查找当前agg值的出现次数,这个次数直接加到最终的答案ans上,因为它表示以当前字符结尾的、符合固定比率的子字符串的数量。然后更新哈希表,将当前agg的计数增加1。这种方法通过在一次遍历中计算并累加符合条件的子字符串数量,避免了复杂的嵌套循环。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在前缀和加哈希表的方法中,为什么初始化`cnt[0]`为1,这代表了什么意义?
▷🦆
如果num1和num2的值非常大,会对哈希表的大小和性能有什么影响?
▷🦆
此算法中,更新`agg`的操作为什么可以保证每个子字符串的比率固定,能否详细解释其数学原理?
▷