计算没有重复字符的子字符串数量
难度:
标签:
题目描述
代码结果
运行时间: 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作为初始值?这个值在算法逻辑中起到了什么作用?
▷🦆
在更新左指针`left`时,为什么要将其设置为`last_occurrence[char] + 1`?这样做的目的是什么?
▷🦆
算法描述中提到对于每个位置的右指针,计算从当前左指针到右指针之间的子字符串数量。请问为什么可以通过`right - left + 1`来直接计算子字符串的数量?
▷🦆
这种算法在处理具有重复字符的字符串时,是否能有效地更新左指针以避免重复子字符串的计算?能否给出一个具体的例子说明?
▷