/** * * @param S string字符串 * @param T string字符串 * @return string字符串 */ function minWindow( S , T ) { // write code here if(S==''||T.length>S.length||T==''){ return "" } let minLen = S.length+1 // 必须加一,不然当S.length==1 T.length==1的时候不生效 let left = 0 let right = 0 let res = "" let count =0 let needs = new Array(128) //needs代表需求的key value对 let windows = new Array(128) //windows代表滑动窗口的key value对 for(let i=0;i<128;i++){ needs[i]=0 windows[i]=0 } for(let i=0;i<T.length;i++){ needs[T[i].charCodeAt()]++ //让needs的key value对根据传入的值来初始化 } while(right<S.length){ let Schar=S[right].charCodeAt() //获取当前右指针所在位置的charcode if(needs[Schar]>0&&needs[Schar]>windows[Schar]){ //如果charcode对应的需求数组里面含有正在遍历的这个值,并且需求的个数大于窗口内的个数,我们就可以开始把匹配到的数值加一用来判断是否达到匹配临界点 //需求数组比windows数组大的临界点在窗口已经饱和满足需求字符个数,也就是说,当次循环状态已经满足了需求个数,不可以去加已匹配字符个数,如果加多了则可能导致内循环永久不能执行. count++ } windows[Schar]++ //和上一行的大于号关联,因为每次是先判断,后执行加操作,所以上面一行为大于号 while(count==T.length){ //在匹配临界的时候,就左移左指针 let Lchar =S[left].charCodeAt() //获取当前右指针所在位置的charcode windows[Lchar]-- //在这里提前减减的好处是下面写法与外层判断一致,如果要理解上下widnows--的位置为什么不同,可以想想,这个条件判断相同的时候,面对的是同一个窗口,那么在判断窗口和需求字符的时候,理论是需要一模一样的窗口数组,这样状态改变是可信的. if(needs[Lchar]>0&&needs[Lchar]>windows[Lchar]){ //判断需求数组里面的左指针是否包含在需求数组里面,并且需求数组的对应包含charcode的个数要大于窗口中的charcode个数,这个判断表示的是当前窗口所包含的此字符出现个数小于需要的此字符出现个数 count-- } if(right-left+1<minLen){ minLen=right-left+1 res=S.substring(left,right+1) console.log(right,left,'nei') } left++ } right++ } return res } module.exports = { minWindow : minWindow };