文章目錄

• 前言
• 一、無(wú)重復(fù)字符的最長(zhǎng)子串
• • 思路 1：
  • 思路 2：
• 二、字符串的排列
• • 思路 1：
  • 思路 2：
  • 思路 3：
  • 思路 3 plus：
  • 思路 3 plus plus：
  • 思路 4：
  • 思路 5：
• 總結(jié)

---

前言

??????Leetcode算法系列：https://leetcode-cn.com/study-plan/algorithms/?progress=njjhkd2

??????簡(jiǎn)單總結(jié)一下滑動(dòng)窗口相關(guān)的算法題：

一、無(wú)重復(fù)字符的最長(zhǎng)子串

??????題目鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

??????題目描述：給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

思路 1：

??????用一個(gè)區(qū)間（窗口）來(lái)表示當(dāng)前的無(wú)重復(fù)字符串，每當(dāng)區(qū)間擴(kuò)大1位的時(shí)候，需要判斷當(dāng)前擴(kuò)充的元素和區(qū)間中哪位元素發(fā)生重復(fù)，不發(fā)生重復(fù)，區(qū)間長(zhǎng)度加一；否則從重復(fù)元素的下一個(gè)元素作為區(qū)間的起始點(diǎn)，當(dāng)前擴(kuò)充的元素作為區(qū)間的結(jié)束點(diǎn)。依次遍歷所有元素。

public int lengthOfLongestSubstring(String s) {int i=0,end=s.length(),start=0;//i 遍歷整個(gè)字符串；start 為區(qū)間起始點(diǎn)。int tmp=0,ans=0;//tmp 為當(dāng)前合法區(qū)間的長(zhǎng)度，ans 為以往合法區(qū)間長(zhǎng)度的最大值。while(i<end){int re=isNotDup(s,start,i);if(re==-1)tmp++;else{ans=tmp>ans?tmp:ans;tmp=i-re+1;start=re;//設(shè)置起點(diǎn)。}i++;}return ans>tmp?ans:tmp;}public int isNotDup(String a,int i,int j){while(i<j){if(a.charAt(i)==a.charAt(j))return i+1;i++;}return -1;}

??????時(shí)間復(fù)雜度為 O(n2)。

思路 2：

??????關(guān)于如何判斷是否發(fā)生重復(fù)，以及設(shè)置區(qū)間的下一個(gè)起點(diǎn)，可以采用 Set 來(lái)做，如果發(fā)生重復(fù)的話：從上一個(gè)區(qū)間的起點(diǎn)依次將元素移出集合，直到不重復(fù)為止。參考算法如下：

public int lengthOfLongestSubstring(String s) {Set<Character> container=new HashSet<>();int i=0,end=s.length(),start=0;int tmp=0,ans=0;while(i<end){if(!container.add(s.charAt(i))){tmp=container.size();ans=ans<tmp?tmp:ans;for(int j=start;j<i;j++){container.remove(s.charAt(j));if(container.add(s.charAt(i))){start=j+1;break;}}}i++;}return ans>container.size()?ans:container.size();}

??????時(shí)間復(fù)雜度為 O(n2)。但是它的執(zhí)行效率沒(méi)有算法1 快。

二、字符串的排列

??????題目鏈接：https://leetcode-cn.com/problems/permutation-in-string/

??????題目描述：給你兩個(gè)字符串 s1 和 s2 ，寫(xiě)一個(gè)函數(shù)來(lái)判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。

換句話說(shuō)，s1 的排列之一是 s2 的 子串 。

思路 1：

??????直觀上，對(duì) s1 求得全排列，然后分別對(duì) s1 的所有排列驗(yàn)證是 s2 的子串。為了回顧 Kmp 和 全排列算法，參考代碼如下：（但它的時(shí)間復(fù)雜度太高，在此不建議使用）

public boolean checkInclusion(String s1, String s2) {//方法1：得到s1的全排列組合， 再采用kmp判斷每個(gè)s1是否為s2的子串。 超出內(nèi)存限制if(s1.length()>s2.length())return false;ArrayList<String> re=new ArrayList<>();arrange(re,s1.toCharArray(),0,s1.length()-1);for(String tmp:re){if(kmp(tmp,s2))return true;}return false;}public static boolean kmp(String s1,String s2){ //s1是否為s2的子串//求next數(shù)組。// -1表示用s1中的第一個(gè)字符匹配s2的下一個(gè)字符；非負(fù)數(shù)表示用s1對(duì)應(yīng)next中的值再次匹配當(dāng)前值。int len=s1.length();int[] next=new int[len];next[0]=-1;int i=0,tmp;while(++i<len){tmp=next[i-1];if(tmp==-1){//簡(jiǎn)化：不需要考慮 s1(0) 和 s1(1) 相等的情況。next[i]=0;continue;}while(tmp!=-1&&s1.charAt(i-1)!=s1.charAt(tmp))tmp=next[tmp];next[i]=tmp+1;}//開(kāi)始匹配int index1=0,index2=0;while(index2<s2.length()){while(s2.charAt(index2)!=s1.charAt(index1)){index1=next[index1];if(index1==-1)break;}index2++;index1++;if(index1==len)return true;}return false;}//全排列：public void arrange(ArrayList<String> re,char[] a,int start,int end){if(start==end)re.add(new String(a)); //采用a構(gòu)建一個(gè)String對(duì)象。else {int index=start;char tmp;while(index<=end){tmp=a[index];a[index]=a[start];a[start]=tmp;arrange(re,a,start+1,end);tmp=a[index];a[index]=a[start];a[start]=tmp;index++;}}}

思路 2：

??????以 s1 的第一個(gè)字符為基準(zhǔn)，找到該字符在 s2 中每一次出現(xiàn)的位置 a0、a1、a2… ，且假設(shè) s1 的長(zhǎng)度為 len，那么在 a0 處從區(qū)間【a0-len+1，a0】直到【a0，a0+len-1】都有可能是 s1 的一個(gè)排列，其余的 a1，a2也是一樣。對(duì)區(qū)間【a0-len+1，a0】直到【a0，a0+len-1】中的元素分別進(jìn)行排序和排序后的 s1 比較判斷是否相等。參考算法如下（其時(shí)間復(fù)雜度依然太高）：

public boolean checkInclusion(String s1, String s2) {int len1=s1.length(),len2=s2.length();if(len1>len2)return false;int start,end;for(int j=0;j<len2;j++){if(s1.charAt(0)==s2.charAt(j)){//從最左區(qū)間開(kāi)始判斷start=j-len1+1;end=j;if(start<0){end=len1-1;start=0;}for(;end<len2;start++,end++){if(decide(s1,s2.substring(start,end+1)))return true;}}}return false;}public boolean decide(String a,String b){char[] aa=a.toCharArray();char[] bb=b.toCharArray();Arrays.sort(aa);Arrays.sort(bb);if(Arrays.equals(aa,bb))return true;return false;}

思路 3：

??????在 2 的基礎(chǔ)上，對(duì)區(qū)間【a0-len+1，a0】直到【a0，a0+len-1】中的元素和 s1 的比較采用統(tǒng)計(jì)字符個(gè)數(shù)的方法來(lái)判斷是否相等。參考算法如下（其時(shí)間復(fù)雜度也比較高）：

public boolean checkInclusion(String s1, String s2) {int len1=s1.length(),len2=s2.length();if(len1>len2)return false;int start,end;int[] count1=new int[26];int[] count2=new int[26];for(int j=0;j<len2;j++){if(s1.charAt(0)==s2.charAt(j)){//從最左區(qū)間開(kāi)始判斷start=j-len1+1;end=j;if(start<0){end=len1-1;start=0;}for(;end<len2;start++,end++){Arrays.fill(count1,0);Arrays.fill(count2,0);if(decide(s1,s2.substring(start,end+1),count1,count2))return true;}}}return false;}public boolean decide(String a,String b,int[] count1,int[] count2){//采用判斷字符的個(gè)數(shù)是否相同的方法驗(yàn)證a是否為b的某個(gè)排列。for(int i=0;i<a.length();i++){count1[a.charAt(i)-'a']++;count2[b.charAt(i)-'a']++;}if(Arrays.equals(count1,count2))return true;return false;}

思路 3 plus：

??????首先沒(méi)必要每次都初始化數(shù)組 count1，它只需要初始化一次即可，其次對(duì)于 count2 沒(méi)必要進(jìn)行整體上的改變，每次只需要增加新元素的個(gè)數(shù)，減少舊元素的個(gè)數(shù)。參考算法如下：

public boolean checkInclusion(String s1, String s2) {int len1=s1.length(),len2=s2.length();if(len1>len2)return false;int start,end;int[] count1=new int[26];for(int i=0;i<len1;i++)count1[s1.charAt(i)-'a']++;int[] count2=new int[26];for(int j=0;j<len2;j++){if(s1.charAt(0)==s2.charAt(j)){//從最左區(qū)間開(kāi)始判斷start=j-len1+1;end=j;if(start<0){end=len1-1;start=0;}//count2 初始化：Arrays.fill(count2,0);for(int i=start;i<=end;i++)count2[s2.charAt(i)-'a']++;if(Arrays.equals(count1,count2))return true; int tmp=j+len1-1;for(start++,end++;end<len2&&end<=tmp;start++,end++){count2[s2.charAt(end)-'a']++;count2[s2.charAt(start-1)-'a']--;if(Arrays.equals(count1,count2))return true; }}}return false;}

思路 3 plus plus：

??????上面算法雖然相比于之前的算法有了更好的運(yùn)行效率。但是此算法的效率沒(méi)有直接在字符串 s2 上采用滑動(dòng)窗口的方法高，原因在于上面的算法在區(qū)間有重復(fù)計(jì)算和比較。在 s2 直接采用滑動(dòng)窗口的算法參考如下：

public boolean checkInclusion(String s1, String s2) {int n = s1.length(), m = s2.length();if (n > m) {return false;}int[] cnt1 = new int[26];int[] cnt2 = new int[26];for (int i = 0; i < n; ++i) {++cnt1[s1.charAt(i) - 'a'];++cnt2[s2.charAt(i) - 'a'];}if (Arrays.equals(cnt1, cnt2)) {return true;}for (int i = n; i < m; ++i) {++cnt2[s2.charAt(i) - 'a'];--cnt2[s2.charAt(i - n) - 'a'];if (Arrays.equals(cnt1, cnt2)) {return true;}}return false;}

思路 4：

??????上面算法有一個(gè)缺點(diǎn)：因?yàn)?ct2 每次各增減一個(gè)字符的個(gè)數(shù)，但是卻對(duì) ct1 和 ct2 整體作比較，優(yōu)化一下，那么需要用一個(gè)變量 diff 來(lái)表示 ct1 和 ct2 之間的差異性，如果 diff 為 0，則二者相等，返回 true；如果不相等，需要繼續(xù)在 s2 上進(jìn)行增減一個(gè)字符操作。差異性可以用 ct2 - ct1 得到，如果相減之后的數(shù)組元素均為 0，則二者相等，diff 也為0，否則初始時(shí)的 diff 為相減之后數(shù)組元素不為 0 的個(gè)數(shù)。

??????這個(gè)數(shù)組用 cnt 來(lái)表示。當(dāng)結(jié)果返回 true 時(shí)對(duì)應(yīng)的是 cnt 中的元素均為 0（diff 為 0），如果 cnt 中的數(shù)為負(fù)，意味 ct2 中的字符沒(méi)有對(duì)應(yīng)的 ct1 中的字符，則需要增加一個(gè)對(duì)應(yīng)的字符；如果為正，意味著 ct2 中的字符是多余的，需要減去一個(gè)對(duì)應(yīng)的字符。

??????在每次窗口滑動(dòng)時(shí)，增加一個(gè)字符需要判斷 cnt[該字符]+1 之后是否為 0，如果為 0，令 diff 減一；減少的字符同理。如果 diff 為 0，證明已找到結(jié)果了。

??????最終：參考算法：

public boolean checkInclusion(String s1, String s2) {int len1=s1.length(),len2=s2.length();if(len1>len2)return false;int[] cnt=new int[26];int diff=0;for(int i=0;i<len1;i++){cnt[s2.charAt(i)-'a']++;cnt[s1.charAt(i)-'a']--;}for(int i=0;i<cnt.length;i++)if(cnt[i]!=0)diff++;if(diff==0)return true;for(int i=len1;i<len2;i++){int addIndex=s2.charAt(i)-'a',minusIndex=s2.charAt(i-len1)-'a';if(addIndex==minusIndex)continue;if(cnt[addIndex]==0)//如果原來(lái)的值為 0，diff需要加一。diff++;if(++cnt[addIndex]==0)//增加一個(gè)字符，對(duì)應(yīng)個(gè)數(shù)加一。加完之后若為0，diff需要減一diff--;if(cnt[minusIndex]==0)diff++;if(--cnt[minusIndex]==0)diff--;if(diff==0)return true;}return false;}

思路 5：

??????在思路 4 的基礎(chǔ)上修改一下，用雙指針的思路來(lái)做，初始時(shí) left 和 right 指針均為 0，表示僅包含在 s2 上的第一個(gè)元素。初始化時(shí) cnt 數(shù)組中的所有值要不為 0，要不小于 0（僅用 cnt[s1.charAt(i)-‘a(chǎn)’]–;來(lái)初始化）。

??????遍歷：右指針一次遍歷，增加的元素如果令對(duì)應(yīng) cnt 中的數(shù)為 <= 0，繼續(xù)；如果 >0 時(shí)，則在當(dāng)前左右指針?biāo)鶚?gòu)成的區(qū)間中，當(dāng)前元素是多余的，此時(shí)需要讓左指針不斷右移，去掉一個(gè)當(dāng)前元素。

??????返回 true 的條件是：某一時(shí)刻 左右指針?biāo)鶚?gòu)成的區(qū)間長(zhǎng)度等于 s1。參考算法：

public boolean checkInclusion(String s1, String s2) {int len1=s1.length(),len2=s2.length();if(len1>len2)return false;int[] cnt=new int[26];int left=0,right=0,addIndex;for(int i=0;i<len1;i++)cnt[s1.charAt(i)-'a']--;while(right<len2){addIndex=s2.charAt(right)-'a';++cnt[addIndex];while(cnt[addIndex]>0){cnt[s2.charAt(left)-'a']--;left++;}if(right-left+1==len1)return true;right++;}return false;}

?????? 效率上，最后的雙指針要優(yōu)于之前的解法，算法也比較簡(jiǎn)潔。

---

總結(jié)

??????完。

總結(jié)

以上是生活随笔為你收集整理的LeetCode算法题6：滑动窗口*的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。