力扣滑動窗口題目總結

Leetcode3.無重復字符的最長子串

思路：
這道題主要用到思路是：滑動窗口

什么是滑動窗口？

其實就是一個隊列,比如例題中的 abcabcbb，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！

如何移動？

我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！

一直維持這樣的隊列，找出隊列出現最長的長度時候，求出解！

時間復雜度：O(n)

力扣官方題解說明：

方法2：滑動窗口法

思路：

我們使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界，其中左指針代表著上文中「枚舉子串的起始位置」，而右指針即為上文中的 rk。

在每一步的操作中，我們會將左指針向右移動一格，表示我們開始枚舉下一個字符作為起始位置，然后我們可以不斷地向右移動右指針，但需要保證這兩個指針對應的子串中沒有重復的字符。在移動結束后，這個子串就對應著以左指針開始的，不包含重復字符的最長子串。我們記錄下這個子串的長度；

在枚舉結束后，我們找到的最長的子串的長度即為答案。

--判斷重復字符：

在上面的流程中，我們還需要使用一種數據結構來判斷是否有重復的字符，常用的數據結構為哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指針向右移動的時候，我們從哈希集合中移除一個字符，在右指針向右移動的時候，我們往哈希集合中添加一個字符。

至此，我們就完美解決了本題。

代碼如下：

class Solution {//這道題主要用到思路是：滑動窗口// 定義一個方法來計算字符串中無重復字符的最長子串長度public int lengthOfLongestSubstring(String s) {//定義一個哈希集合，記錄每個字符是否出現過（HashSet無序不可重復）Set<Character> occ = new HashSet<>(); //Charccter是Char的包裝類int n = s.length();//右指針，初始值為-1，相當于我們在字符串的左邊界的左側，還沒有開始移動int r = -1,res = 0;for(int i = 0; i < n; i ++){if(i != 0){//左指針向右移動一格，移除一個字符occ.remove(s.charAt(i-1));}//不斷移動右指針，直到遇到重復字符或者到達字符串末尾while(r + 1 < n && !occ.contains(s.charAt(r+1))){//沒到字符串末尾 && 不包含r+1-->將字符添加到集合中occ.add(s.charAt(r+1));//右指針右移++r;}//更新答案，取當前最大無重復子串的長度res = Math.max(res, r - i + 1);}// 返回結果，即最長無重復子串的長度return res;}
}

這段代碼使用了滑動窗口技術，通過移動兩個指針（左指針 i 和右指針 r）來尋找最長的無重復字符子串。具體操作如下：

初始化一個字符集合 occ 用于記錄當前窗口中包含的字符。
定義右指針 r?的初始值為 -1，表示它還沒有開始移動，并定義結果變量res?用于存儲最長子串的長度。
通過外層 for 循環移動左指針 i，逐個處理字符串中的字符。
如果左指針 i 不是在初始位置，則移除左指針前一個位置的字符 s.charAt(i - 1)，以確保當前窗口只包含無重復字符。
使用 while 循環不斷右移右指針 r，擴展當前窗口，直到遇到重復字符或到達字符串末尾。每次右移時，將當前字符添加到集合 occ 中。
在每次擴展窗口后，更新結果 res?為當前窗口長度（r - i + 1）與之前最大長度中的較大值。
最終返回結果 res，即最長無重復字符子串的長度。

?補充知識點：

在Java中，Character 是一個包裝類（wrapper class），它封裝了一個基本類型 char 的值。Character 類提供了一些方法來操作字符數據類型。與 char 不同，Character 是一個類，可以用于泛型集合（如 Set、List 等），因為這些集合只能包含對象，而不能包含基本數據類型。

下面是一些關于 Character 類的關鍵點：

封裝基本類型 char：

char 是一個基本數據類型，表示單個16位Unicode字符。
Character 類將 char 封裝為對象，使其能夠在需要對象的上下文中使用。

創建 Character 對象：
可以通過構造器或自動裝箱（autoboxing）將 char 值轉換為 Character 對象。
char ch = 'a';
Character characterObject = new Character(ch); // 使用構造器
Character characterObject2 = ch; // 自動裝箱
?????3.常用方法：

Character 類提供了許多實用方法來處理字符。例如：
Character.isDigit(char ch): 檢查字符是否為數字。
Character.isLetter(char ch): 檢查字符是否為字母。
Character.toUpperCase(char ch): 將字符轉換為大寫。
Character.toLowerCase(char ch): 將字符轉換為小寫。

438.找到字符串中所有字母異位詞

class Solution {// 定義一個方法來查找字符串 s 中所有是字符串 p 的字母異位詞的子串的起始索引public List<Integer> findAnagrams(String s, String p) {// 獲取字符串 s 和 p 的長度int n = s.length(), m = p.length();// 結果列表，用于存儲所有符合條件的起始索引List<Integer> res = new ArrayList<>();// 如果 s 的長度小于 p 的長度，直接返回空列表if(n < m) return res;// 定義兩個數組，用于記錄 p 和 s 當前窗口中字符的頻率int[] pCnt = new int[26];int[] sCnt = new int[26];// 初始化頻率數組，將 p 和 s 前 m 個字符的頻率記錄到各自的數組中for(int i = 0; i < m; i++){pCnt[p.charAt(i) - 'a']++;sCnt[s.charAt(i) - 'a']++;}// 檢查初始窗口（s 的前 m 個字符）是否與 p 匹配，如果匹配，將索引 0 加入結果列表if(Arrays.equals(sCnt, pCnt)){res.add(0);}// 遍歷字符串 s，從索引 m 開始，每次向右滑動一個字符for(int i = m; i < n; i++){// 移除左邊界字符的頻率（滑動窗口左移）sCnt[s.charAt(i - m) - 'a']--;// 添加右邊界字符的頻率（滑動窗口右移）sCnt[s.charAt(i) - 'a']++;// 檢查當前窗口是否與 p 匹配，如果匹配，將起始索引加入結果列表if(Arrays.equals(sCnt, pCnt)){res.add(i - m + 1);}}// 返回結果列表return res;}
}

初始化和邊界檢查：

獲取 s 和 p 的長度。
如果 s 的長度小于 p 的長度，直接返回空列表，因為不可能有異位詞。

頻率數組初始化：

使用兩個大小為 26 的數組 pCnt 和 sCnt 分別記錄 p 和 s 當前窗口中字符的頻率。
初始化頻率數組，記錄 p 和 s 前 m 個字符（p 的長度）的頻率。

初始窗口匹配檢查：

檢查 s 的前 m 個字符是否與 p 匹配，如果匹配，將索引 0 加入結果列表。

滑動窗口遍歷：

從索引 m 開始遍歷 s，每次滑動窗口右移一個字符：
減少左邊界字符的頻率（移出窗口）。
增加右邊界字符的頻率（加入窗口）。
檢查當前窗口是否與 p 匹配，如果匹配，將起始索引加入結果列表。

返回結果：

返回包含所有符合條件的起始索引的結果列表。

代碼深度解釋：

當 i 從 m 開始遍歷到 n-1 時，代表滑動窗口的右邊界每次右移一個字符，這兩行代碼分別是在這個過程中執行的操作。

sCnt[s.charAt(i - m) - 'a']--;：這行代碼是為了移除左邊界字符的頻率。在滑動窗口右移時，窗口的左邊界向右移動一個字符，因此需要將移出窗口的左邊界字符在 sCnt 數組中的計數減去 1。

sCnt[s.charAt(i) - 'a']++;：這行代碼是為了添加右邊界字符的頻率。在滑動窗口右移時，窗口的右邊界向右移動一個字符，因此需要將新加入窗口的右邊界字符在 sCnt 數組中的計數加上 1。

這兩步操作保證了每次窗口的頻率數組 sCnt 都能正確地反映當前窗口中字符的頻率情況，以便后續比較是否與 p 的頻率數組 pCnt 相同，從而判斷是否滿足異位詞的條件。

class Solution {// 定義一個方法來查找字符串 s 中所有是字符串 p 的字母異位詞的子串的起始索引public List<Integer> findAnagrams(String s, String p) {// 獲取字符串 s 和 p 的長度int n = s.length(), m = p.length();// 結果列表，用于存儲所有符合條件的起始索引List<Integer> res = new ArrayList<>();// 如果 s 的長度小于 p 的長度，直接返回空列表if (n < m) return res;// 定義兩個數組，用于記錄 p 和 s 當前窗口中字符的頻率int[] pCnt = new int[26];int[] sCnt = new int[26];// 初始化 p 的頻率數組，將 p 的每個字符的頻率記錄到 pCnt 數組中for (int i = 0; i < m; i++) {pCnt[p.charAt(i) - 'a']++;}// 定義左指針，初始值為 0int left = 0;// 遍歷字符串 s，每次右指針右移一個字符for (int right = 0; right < n; right++) {// 獲取右指針當前字符在字母表中的索引int curRight = s.charAt(right) - 'a';// 增加當前右指針字符在 sCnt 數組中的頻率sCnt[curRight]++;// 如果當前右指針字符的頻率超過了 p 中該字符的頻率，需要縮小窗口while (sCnt[curRight] > pCnt[curRight]) {// 獲取左指針當前字符在字母表中的索引int curLeft = s.charAt(left) - 'a';// 減少當前左指針字符在 sCnt 數組中的頻率sCnt[curLeft]--;// 左指針右移一格left++;}// 如果當前窗口的長度等于 p 的長度，說明找到了一個異位詞if (right - left + 1 == m) {// 將當前窗口的起始索引加入結果列表res.add(left);}}// 返回結果列表return res;}
}

這段代碼使用了滑動窗口和字符頻率計數技術來查找字符串 s 中所有是字符串 p 的字母異位詞的子串的起始索引。具體操作如下：

初始化和邊界檢查：

獲取 s 和 p 的長度。
如果 s 的長度小于 p 的長度，直接返回空列表，因為不可能有異位詞。

頻率數組初始化：

使用一個大小為 26 的數組 pCnt 記錄 p 中每個字符的頻率。
使用一個大小為 26 的數組 sCnt 來記錄當前滑動窗口中字符的頻率。

滑動窗口遍歷：

使用兩個指針 left 和 right 表示當前滑動窗口的左右邊界。
右指針 right 從 0 開始遍歷 s，每次右移一個字符，將該字符在 sCnt 數組中的頻率加 1。
如果當前字符的頻率超過了 p 中該字符的頻率，進入 while 循環，通過移動左指針 left 來縮小窗口，直到當前字符的頻率不超過 p 中該字符的頻率為止。
如果當前窗口的長度等于 p 的長度，說明找到了一個異位詞，將窗口的起始索引 left 加入結果列表。

返回結果：

返回包含所有符合條件的起始索引的結果列表。