leetcode
leetcode 2201 ~ 2250
固定比率的子字符串数

固定比率的子字符串数

难度:

标签:

题目描述

代码结果

运行时间: 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,这代表了什么意义?
在使用前缀和方法解题时,初始化`cnt[0]`为1是非常重要的一步。这是因为`cnt[0] = 1`代表了在任何字符被处理之前,累加器`agg`的值为0的一个有效状态。这允许算法正确地计算从字符串起始到当前位置的累加值正好为0的子字符串。例如,如果字符串的前几个字符累计值正好抵消为0,那么这些字符形成的子字符串就是一个有效的符合要求的字符串,它的存在需要通过`cnt[0]`来识别。简而言之,`cnt[0] = 1`确保了从字符串开头到当前位置的累加值为0的情况被正确计算。
🦆
如果num1和num2的值非常大,会对哈希表的大小和性能有什么影响?
当`num1`和`num2`的值非常大时,累加器`agg`的值变化幅度也会随之增大,这可以导致哈希表中存储的不同累加值数量显著增加。哈希表的大小直接依赖于这些不同累加值的数量。较大的`num1`和`num2`值可能使`agg`在每一步变化更大,从而产生更多独特的累加值。这种增加可能导致哈希表需要更多内存来存储这些值,并且在哈希表中查找、插入和更新操作的性能可能会随着哈希表大小的增加而降低,特别是如果哈希冲突增多时。因此,如果`num1`和`num2`非常大,可能需要优化哈希表的处理方式,例如通过使用更有效的哈希函数来减少冲突,或者考虑其他数据结构来优化性能。
🦆
此算法中,更新`agg`的操作为什么可以保证每个子字符串的比率固定,能否详细解释其数学原理?
此题的核心是使用累加器`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`的值,我们能够识别和计算符合特定比率的子字符串,这是通过巧妙地利用前缀和的性质和哈希表的快速查找能力实现的。

相关问题