当前位置：首页 > news >正文

【力扣 Hot100】滑动窗口巧解字串问题

news 2025/8/22 22:34:05

D13

无重复字符的最长字串

3. 无重复字符的最长子串 - 力扣（LeetCode）

这道题目是典型的滑动窗口问题，核心为：

用两个指针left和right维护一个窗口

right不断向右扩展，尝试加入新的字符
如果加入字符导致重复，移动left，缩小窗口，直到重复值被除掉。
每次都更新窗口的最大值

class Solution {public int lengthOfLongestSubstring(String s) {char[] chars = s.toCharArray(); //转化为char数组便于操作int left = 0; //窗口左端点int[] cnt = new int[128]; // ASCII字符频率统计(包含全部ASCII字符)int ans = 0; // 记录最大长度for (int right = 0; right < chars.length; right++) {char c = chars[right];cnt[c]++; // 记录某字符的重复次数while(cnt[c] > 1){cnt[chars[left]]--; // 除掉重复值，移动窗口left++;}ans = Math.max(ans, right - left + 1); // 最长重复子串}return ans;}
}

这里需要注意的是，一定是先除掉重复值，再移动left。要先减掉重复值的记数，再移动窗口。否则先移动窗口后，窗口边缘的值已经改变，减去的就是其他字符的记数次数。

定长字串中元音的最大数目

1456. 定长子串中元音的最大数目 - 力扣（LeetCode）

这个题目是一道定长滑窗，介绍一下灵神的套路：

定长滑窗套路

窗口右端点在 i 时，由于窗口长度为 k，所以窗口左端点为 i−k+1。

总结成三步：入-更新-出。

入：下标为 i 的元素进入窗口，更新相关统计量。如果窗口左端点 i−k+1<0，即 i<k−1，则尚未形成第一个窗口，重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量，为下一个循环做准备。

以上三步适用于所有定长滑窗题目。

class Solution {public int maxVowels(String s, int k) {char[] chars = s.toCharArray();int ans = 0;int cnt = 0;for (int i = 0; i < chars.length; i++) {// 入char c = chars[i];if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cnt++;if(i < k - 1) continue; // 窗口大小不够，还未形成第一个窗口// 更新ans = Math.max(ans, cnt);// 移出左端元素char l = chars[i - k + 1];if(l == 'a' || l == 'e' || l == 'i' || l == 'o' || l == 'u') cnt--;}return ans;}
}

找出字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

解答这道题目时建议先看一下上一题定长滑窗的套路，这个题目实际上是找出s中长度为p.length的字串，作为窗口，判断字串的字母是否和p中相同（不考虑各字母的位置）

那么把套路应用到这个题目就是：

前提：对p的统计数组cntP，对s的统计数组cntS

入：从头开始遍历s，记为right，将字母加入到窗口，直到窗口大小与p.length相等，left = right - p.length + 1 > 0。
更新：如果cntS与cntP相等，那么说明窗口与p时字母异位词，记录起始索引left
出：移出cntS[left]

按照这个思路代码如下：

class Solution {public List<Integer> findAnagrams(String s, String p) {int[] cntS = new int[26];int[] cntP = new int[26];char[] pc = p.toCharArray();List<Integer> list = new ArrayList<>();// 记录p的字母出现次数for (char c : pc) {cntP[c - 'a']++;}for (int right = 0; right < s.length(); right++) {// 入cntS[s.charAt(right) - 'a']++; // 填充窗口int left = right - p.length() + 1;if(left < 0) continue;// 更新if(Arrays.equals(cntS, cntP)){list.add(left);}cntS[s.charAt(left) - 'a']--;}return list;}
}