为什么网站显示在建设中,wordpress用户中心主题,天津百度分公司,建设网站简单的需要多少天文章目录题目描述思路 代码二刷最近一直在充电基础知识、维护 leetcode 总结博客 今天继续摸一摸新题目吧#xff5e; 题目描述
感觉和 03. 无重复的最长子串 有点像#xff0c;都是在字符串上用滑动窗口来找子串。并且都是属于那种#xff0c;解决一次以后 代码二刷最近一直在充电基础知识、维护 leetcode 总结博客 今天继续摸一摸新题目吧 题目描述
感觉和 03. 无重复的最长子串 有点像都是在字符串上用滑动窗口来找子串。并且都是属于那种解决一次以后思路都十分清晰的类型。
思路 代码
步骤参考了mcdull的这篇题解注意点需要维护的变量很多(need、left、right、count、minSize、startIndex要保证正确维护。need[128] 存储当前滑动窗口对每个字符还需要的数量。为0则正好负数则说明冗余正数则还需要。时间复杂度O(n)也就是最多 right 跑一遍left 跑一遍
class Solution {// 思路滑动窗口 双指针。正确维护几个变量十分重要// 复杂度最多为O(2 * n) O(n)public String minWindow(String s, String t) {if(s null || t null || s.length() 0 || t.length() 0) {return ;}// need总是记录当前窗口每个字符还需的数量。负数为冗余数量int[] need new int[128];for(char c : t.toCharArray()) {need[c];}int count t.length(), startIndex 0, minSize Integer.MAX_VALUE;for(int l 0, r 0; r s.length(); r) {if(need[s.charAt(r)] 0) {count--;}need[s.charAt(r)]--;if(count 0) {// 去掉窗口前段的冗余元素更新 leftwhile(l r need[s.charAt(l)] 0) {need[s.charAt(l)];l;}// 维护 minSizeif(r - l 1 minSize) {minSize r - l 1;startIndex l;}// 继续下一轮的窗口对比need[s.charAt(l)];l;count;}}return minSize Integer.MAX_VALUE ? : s.substring(startIndex, startIndex minSize);}
}二刷
实打实的滑动窗口维护总的来说还是几个变量的维护直接看代码和注释吧
class Solution {public String minWindow(String s, String t) {// 记录字符需要的数量负数冗余int[] need new int[128];for(char c : t.toCharArray()) {need[c];}int counts t.length(), startIndex 0, minSize Integer.MAX_VALUE;for(int l 0, r 0; r s.length(); r) {// Part 1: 更新 counts needif(need[s.charAt(r)] 0) {counts--;}need[s.charAt(r)]--;// Part 2: 此时满足的情况更新窗口if(counts 0) {// Part 2.1去除前面的冗余字符while(l r need[s.charAt(l)] 0) {need[s.charAt(l)];l;}// Part 2.2维护 minSizeif(r - l 1 minSize) {startIndex l;minSize r - l 1;}// Part 2.3进行下一轮维护need[s.charAt(l)];counts;}}return minSize Integer.MAX_VALUE ? : s.substring(startIndex, startIndex minSize);}
}
