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

LeetCode Hot100 - 滑动窗口篇

news 2025/6/17 11:03:03

前言

挑战一个月刷完力扣的hot100，记录一下每题的思路~

这次是滑动窗口相关的题目

（1）3. 无重复字符的最长子串

双指针+变长滑动窗口。若已知一个不重复子串(l到r)，右指针扩充一个(r+1)，只可能r+1与某个k重复，因为l到k的字符不可能再产生新的更长不重复子串，于是将l循环收缩，直至新字符不重复(即l收缩到k+1)，。然后r再继续往后扩充找新子串

class Solution {Set<Character> set = new HashSet<>();public int lengthOfLongestSubstring(String s) {int res=0;// 每次右指针加一个for(int l=0,r=0; r<s.length(); r++){// 若当前元素已包含，循环缩短左边界，直至不在set中while(set.contains(s.charAt(r)))set.remove(s.charAt(l++));set.add(s.charAt(r)); // 添加当前元素res = Math.max(res,r-l+1); // 保留最长串}return res;}
}

（2）438. 找到字符串中所有字母异位词

①定长滑动窗口。窗口长度始终为pLen，使用长度26的数组记录滑动窗口和p的字符数量，不断后移滑动窗口比较是否为异位词

class Solution {int[] sCount = new int[26], pCount = new int[26]; // 计数List<Integer> res = new ArrayList<>();public List<Integer> findAnagrams(String s, String p) {int sLen=s.length(), pLen=p.length();if(sLen<pLen)return res; // 长度不足for(int i=0; i<pLen; i++){ // 初始化计数数组++sCount[s.charAt(i)-'a'];++pCount[p.charAt(i)-'a'];}if(Arrays.equals(sCount,pCount))res.add(0); // 异位词for(int i=0;i<sLen-pLen;i++){ // 滑动窗口长度始终为pLen--sCount[s.charAt(i)-'a'];++sCount[s.charAt(i+pLen)-'a'];if(Arrays.equals(sCount,pCount))res.add(i+1);}return res;}
}

②双指针+变长滑动窗口。用count记录p与滑动窗口差值，计数p初始化count。用双指针遍历，r右移取一位，维护count不小于0，循环收缩左边界。若滑动窗口长度与p同，且count不小于0，即每个元素相同，记录l

class Solution {int[] count = new int[26]; // 计数，p与滑动窗口差值List<Integer> res = new ArrayList<>();public List<Integer> findAnagrams(String s, String p) {int sLen=s.length(), pLen=p.length();if(sLen<pLen)return res; // 长度不足for(char c:p.toCharArray()) ++count[c-'a']; // 初始化计数数组for(int l=0,r=0; r<sLen; r++){ // 双指针遍历--count[s.charAt(r)-'a']; // 取r// 循环收缩左边界，维持每个元素不小于0while(count[s.charAt(r)-'a']<0) ++count[s.charAt(l++)-'a'];// 长度相同，且每个元素不小于0，即个数相同if(r-l+1==pLen)res.add(l);}return res;}
}