算法练习题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;
        }
}

原文地址：https://blog.csdn.net/2302_78946634/article/details/142444218

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！