滑动窗口
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。也可以理解为一种双指针的做法。
leetcode76
class Solution {public String minWindow(String s, String t) {char[] schars = s.toCharArray();char[] tchars = t.toCharArray();int []sint=new int[123];int []tint=new int[123];for (int i=0;i<tchars.length;i++){tint[tchars[i]]++;}int l=0;int r=schars.length;int distance=0;int begin=0;int min=schars.length+1;for(int i=0;i<r;i++){if(tint[schars[i]]==0){continue;}else{if(sint[schars[i]]<tint[schars[i]]){distance++;}sint[schars[i]]++;while (distance==tchars.length){if(i-l+1<min){begin=l;min=i-l+1;}if(tint[schars[l]]==0){l++;continue;}if(sint[schars[l]]==tint[schars[l]]){distance--;}sint[schars[l]]--;l++;}}}if(min==(s.length()+1)){return "";}return s.substring(begin,begin+min);}}