leetcode
leetcode 2401 ~ 2450
计算没有重复字符的子字符串数量

计算没有重复字符的子字符串数量

难度:

标签:

题目描述

代码结果

运行时间: 252 ms, 内存: 16.4 MB


/*
 * 题目思路:
 * 由于Java Stream不直接支持滑动窗口操作,因此我们需要借助IntStream来实现相似的逻辑。
 * 1. 使用IntStream.range创建一个从0到字符串长度的流。
 * 2. 使用双指针和HashSet在forEach中实现滑动窗口的逻辑。
 */
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class UniqueSubstringCounterStream {
    public static int countUniqueSubstrings(String s) {
        Set<Character> set = new HashSet<>();
        final int[] start = {0};
        final int[] count = {0};
        IntStream.range(0, s.length()).forEach(end -> {
            while (set.contains(s.charAt(end))) {
                set.remove(s.charAt(start[0]));
                start[0]++;
            }
            set.add(s.charAt(end));
            count[0] += end - start[0] + 1;
        });
        return count[0];
    }
    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(countUniqueSubstrings(s)); // 输出结果示例
    }
}

解释

方法:

该题解使用了双指针(滑动窗口)的技巧来解决问题。首先定义一个数组 `last_occurrence` 来记录字符串中每个字符最后一次出现的位置。利用一个左指针 `left` 和一个右指针 `right` 遍历字符串。对于每个字符,如果它之前出现过,并且其上次出现的位置大于或等于当前左指针的位置,则将左指针移动到该字符上一次出现位置的下一个位置。然后更新该字符在 `last_occurrence` 中的位置。对于每个位置的右指针,计算从当前左指针到右指针之间的子字符串数量,并累加到结果中。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在初始化`last_occurrence`数组时,为什么选择-1作为初始值?这个值在算法逻辑中起到了什么作用?
在初始化`last_occurrence`数组时,选择-1作为初始值是为了标记所有字符在开始遍历字符串`s`之前都未曾出现过。这个值在算法逻辑中起到关键作用:当我们检查某个字符时,如果它的`last_occurrence`值为-1,意味着该字符在当前`right`指针之前没有出现过,因此不需要移动`left`指针。这样可以保证`left`指针仅在必要时进行移动,从而正确地维护无重复字符的子字符串的边界。
🦆
在更新左指针`left`时,为什么要将其设置为`last_occurrence[char] + 1`?这样做的目的是什么?
当某个字符在`right`指针的当前位置再次出现时,为了确保从`left`到`right`的子字符串中没有重复字符,需要将`left`指针移动到该重复字符上一次出现的位置之后一个位置上(即`last_occurrence[char] + 1`)。这样做的目的是排除掉包含重复字符的子字符串区域,从而维护一个始终不包含重复字符的有效子字符串窗口。
🦆
算法描述中提到对于每个位置的右指针,计算从当前左指针到右指针之间的子字符串数量。请问为什么可以通过`right - left + 1`来直接计算子字符串的数量?
对于每个右指针的位置,以该位置为结束点的所有可能的子字符串起始点为从`left`到`right`。因此,子字符串的数量等于`right`指针位置与`left`指针位置之间的距离加1(即`right - left + 1`)。这是因为每个这样的起始点都会与`right`指针位置形成一个唯一的子字符串。
🦆
这种算法在处理具有重复字符的字符串时,是否能有效地更新左指针以避免重复子字符串的计算?能否给出一个具体的例子说明?
是的,这种算法能有效地更新左指针以避免重复子字符串的计算。例如,字符串`'abca'`中,当处理到第二个`'a'`(位置3)时,`last_occurrence`数组记录的第一个`'a'`的位置是0。由于第二个`'a'`出现时,`left`指针位置是1,`last_occurrence[a]`是0,这大于当前`left`指针位置,因此将`left`指针更新为`last_occurrence[a] + 1`即1+1=2。这避免了从位置1开始的子字符串`'bca'`中的重复字符`'a'`的计算,确保所有计算的子字符串都是没有重复字符的。

相关问题