)
js一刷法一(丑陋)
varminWindow=function(s,t){if(s.length<t.length)return"";letm=newSet(s);for(leti=0;i<t.length;i++){if(!m.has(t[i]))return"";}letans=[0,1000000000000000000];letidx=newMap();for(leti=0;i<t.length;i++){idx.set(t[i],(idx.get(t[i])??0)+1);}letleft=0,right=0;while(right<s.length){if(idx.has(s[right]))idx.set(s[right],idx.get(s[right])-1);while([...idx.values()].every(x=>x<=0)){if(left===right)returns[right];if(right-left<ans[1]-ans[0])ans=[left,right];if(idx.has(s[left]))idx.set(s[left],idx.get(s[left])+1);left++;}right++;}while([...idx.values()].every(x=>x<=0)){if(left===right)returns[right];if(right-left<ans[1]-ans[0])ans=[left,right];if(idx.has(s[left]))idx.set(s[left],idx.get(s[left])+1);left++;}if(ans[1]==1000000000000000000)return"";returns.slice(ans[0],ans[1]+1);};js一刷法一(优化版)
varminWindow=function(s,t){if(s.length<t.length)return"";letneed=t.length;letmap=newMap();for(letcoft){map.set(c,(map.get(c)??0)+1);}letleft=0;letans=[0,Infinity];for(letright=0;right<s.length;right++){letc=s[right];if(map.has(c)){if(map.get(c)>0)need--;map.set(c,map.get(c)-1);}while(need===0){if(right-left<ans[1]-ans[0]){ans=[left,right];}letd=s[left];if(map.has(d)){map.set(d,map.get(d)+1);if(map.get(d)>0)need++;}left++;}}returnans[1]===Infinity?"":s.slice(ans[0],ans[1]+1);};思路完全相同,只不过一开始我是想用之前一个题思路,先将t存入hash,然后遇到符合条件的就-1,优化后用need(t的长度)来记录,need=0时候,说明找到了
算法核心:左指针不动,右指针不断往右,当窗口里包含了所有符合条件的字符后,从左边缩短窗口,左指针右移,所以说left在right动之前,永远指向的是有效字符,因为无效的在循环中清除了
js一刷法二(无敌)
varminWindow=function(s,t){constarr=newArray(128).fill(0);for(constioft){arr[i.charCodeAt(0)]--;}letleft=0,right=0,count=0,start=-1;letlen=s.length+1;while(right<s.length){if(arr[s.charCodeAt(right)]<0){count++;}arr[s.charCodeAt(right)]++;while(left<=right&&arr[s.charCodeAt(left)]>0){arr[s.charCodeAt(left)]--;left++;}if(count===t.length&&right-left+1<len){len=right-left+1;start=left;}right++;}returnstart===-1?"":s.slice(start,start+len);};算法核心:长度可变的滑动窗口,因为字符串中数字大小写字母不方便来比较,所以全部转化成ASCII码来比较,创建一个长度为128的数组,对应0-127的ASCII码,可以表示26个大小写字母,0-9的数字
数组中
>0 无效元素
=0 符合要求,刚好在窗口内
<0 不在窗口内
先把数组全部初始化为0,要找的字符全部初始化为-1,然后向右遍历,并+1,原来为-1的加一后变为0,为在窗口内的有效字符,无用的字符和有用但重复的字符+1后>0,在后续的循环中可以被清除
用start记录起点 用len来更新长度,找到最小的len
语法注意点:
想要获取数组/字符串arr中的一部分,并且不破坏原数组,用slice(i,j),可以将arr[i]~arr[j-1]存储在新数组中并返回
arr.charCodeAt[i] 将arr[i]转化成ASCII码
