佛山移动网站设计,专业制作门户型网站,电脑软件开发是什么专业,校园网站设计参考文献题目描述 解题思路
本题用到了滑动窗口 双指针 哈希
刚开始我是没读懂题的因为我笨
我想把我的思路说一下 左端不轻易缩小 只有找到跟word2匹配了 比如说abbcdd 遍历到c的时候才能匹配这个word2 对吧 那么之后加上以一个d或者俩d 都符合了 然后我们算完了 才能缩小左端 扩大…题目描述 解题思路
本题用到了滑动窗口 双指针 哈希
刚开始我是没读懂题的因为我笨
我想把我的思路说一下 左端不轻易缩小 只有找到跟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 的字符频次MapCharacter, Integer countWord2 new HashMap();for (char c : word2.toCharArray()) {countWord2.put(c, countWord2.getOrDefault(c, 0) 1);}// 滑动窗口的字符频次计数器MapCharacter, 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;}
}
