本次整理三道高频连续子数组/子串经典题3.无重复字符的最长子串滑动窗口438.找到字符串中所有字母异位词定长滑动窗口560.和为K的子数组前缀和哈希无法用滑动窗口核心区分✅ 滑动窗口适用区间满足单调性右边界扩张时左边界只会单向右移❌ 数组存在负数时区间和不具备单调性不能滑动窗口改用前缀和哈希。3. 无重复字符的最长子串题目大意找出字符串中不含重复字符的最长连续子串长度。思路不定长滑动窗口双指针left、rightHashSet维护窗口内字符右指针不断向右扩张遇到重复字符时不断移动左指针并删除窗口内字符直到当前字符不存在窗口中。classSolution{publicintlengthOfLongestSubstring(Strings){char[]sss.toCharArray();// set保存当前窗口[left, right]内所有字符SetCharactersetnewHashSet();intres0;// 右指针持续向右遍历for(intleft0,right0;rights.length();right){charchss[right];// 当前字符已经存在窗口不断收缩左边界while(set.contains(ch)){set.remove(ss[left]);left;}// 将当前右指针字符加入窗口set.add(ss[right]);// 更新最大窗口长度resMath.max(res,right-left1);}returnres;}}关键点while而不是if重复字符可能不在窗口最左侧需要持续左移直到无重复子串必须连续窗口区间[left,right]永远代表合法无重复区间。438. 找到字符串中所有字母异位词题目大意在s中找到所有p的字母异位词子串返回起始下标。异位词字母组成、数量完全相同顺序不同。思路定长滑动窗口窗口长度固定等于p的长度使用数组统计字符频次对比频次数组判断是否为异位词。classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();ListIntegeransnewArrayList();// s长度小于p不可能存在异位词直接返回空集合if(sLenpLen){returnans;}// 频次数组仅小写字母大小26int[]sCountnewint[26];int[]pCountnewint[26];// 初始化第一个窗口填充p长度的字符for(inti0;ipLen;i){sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];}// 第一个窗口匹配成功起始下标0加入结果if(Arrays.equals(sCount,pCount)){ans.add(0);}// 滑动窗口依次向右移动窗口for(inti0;isLen-pLen;i){// 移出窗口最左侧字符sCount[s.charAt(i)-a]--;// 纳入窗口右侧新字符sCount[s.charAt(ipLen)-a];// 频次数组完全相等 字母异位词if(Arrays.equals(sCount,pCount)){ans.add(i1);}}returnans;}}关键点定长窗口窗口宽度固定为p.length字母异位词等价于字符频次完全一致不用排序字符串数组对比效率更高每次滑动只修改左右两个字符的计数不需要重新统计整个窗口。560. 和为 K 的子数组题目大意统计数组中和等于k的连续子数组数量。数组存在负数思路前缀和 哈希表。定义前缀和pre[i] nums[0] nums[1] … nums[i]区间[j1, i]的和 pre[i] - pre[j]我们要求pre[i] - pre[j] k→pre[j] pre[i] - k哈希表记录每个前缀和出现的次数遍历到当前pre时查询pre-k存在多少次就是满足条件的子数组数量。classSolution{publicintsubarraySum(int[]nums,intk){intcount0;// 答案计数intpre0;// 当前前缀和// key前缀和value该前缀和出现次数HashMapInteger,IntegermapnewHashMap();// 初始化前缀和为0出现1次处理pre刚好等于k的场景map.put(0,1);for(inti0;inums.length;i){prenums[i];// 存在pre-k累加对应的出现次数if(map.containsKey(pre-k)){countmap.get(pre-k);}// 更新当前前缀和出现次数map.put(pre,map.getOrDefault(pre,0)1);}returncount;}}关键点数组包含负数区间和不单调不能使用滑动窗口map.put(0,1)必不可少例如nums[1],k1pre1pre-k0需要初始前缀和0先查询再put避免把当前pre计入本次查询保证区间是连续子数组。三道题目对比总结无重复最长子串不定长滑动窗口窗口约束「无重复字符」左右指针单向移动字母异位词定长滑动窗口窗口长度固定使用频次数组快速匹配异位词和为K子数组前缀和哈希。数组有负数时滑动窗口失效属于滑动窗口题的重要边界区分。
)
