算法练习题25——leetcode3279统计重新排列后包含另一个字符串的子字符串的数目（滑动窗口 双指针 哈希）

题目描述

解题思路

本题用到了滑动窗口 双指针 哈希

刚开始我是没读懂题的因为我笨

我想把我的思路说一下 左端不轻易缩小 只有找到跟word2匹配了 比如说abbcdd  遍历到c的时候才能匹配这个word2 对吧 那么之后加上以一个d或者俩d 都符合了 然后我们算完了 才能缩小左端 扩大右端

让left先不动 等字符频次和目标频次完全匹配后 right右边剩余的所有字符都可以加到结果字符串中作为符合的子字符串 然后再移动left

代码示例

class Solution {public long validSubstringCount(String word1, String word2) {int n = word1.length();int m = word2.length();// 统计 word2 的字符频次Map<Character, Integer> countWord2 = new HashMap<>();for (char c : word2.toCharArray()) {countWord2.put(c, countWord2.getOrDefault(c, 0) + 1);}// 滑动窗口的字符频次计数器Map<Character, Integer> countWindow = new HashMap<>();int left = 0;  // 窗口左边界long result = 0;int matched = 0;  // 记录匹配的字符数量// 开始滑动窗口的遍历for (int right = 0; right < n; right++) {// 扩展右端，加入当前字符char rightChar = word1.charAt(right);countWindow.put(rightChar, countWindow.getOrDefault(rightChar, 0) + 1);// 如果该字符在 word2 中存在，且它的频次也匹配了if (countWord2.containsKey(rightChar)) {if (countWindow.get(rightChar).equals(countWord2.get(rightChar))) {matched++;}}// 当窗口中的字符频次与 word2 完全匹配时while (matched == countWord2.size()) {// 计算从当前窗口到字符串末尾的所有合法子串result += (n - right);  // 从 right 到字符串末尾的所有子串都是合法的// 缩小左端，移除左边的字符char leftChar = word1.charAt(left);if (countWindow.get(leftChar) > 0) {countWindow.put(leftChar, countWindow.get(leftChar) - 1);}if (countWord2.containsKey(leftChar)) {if (countWindow.get(leftChar) < countWord2.get(leftChar)) {matched--;  // 如果频次不再匹配，匹配字符数减少}}left++;  // 左端收缩}}return result;}
}