前言

滑動(dòng)窗口類問(wèn)題是面試當(dāng)中的高頻題，問(wèn)題本身其實(shí)并不復(fù)雜瘾晃，但是實(shí)現(xiàn)起來(lái)細(xì)節(jié)思考非常的多贷痪，想著想著可能因?yàn)樽兞孔兓羔樢苿?dòng)等等問(wèn)題蹦误，導(dǎo)致程序反復(fù)刪來(lái)改去劫拢，有思路，但是程序?qū)懖怀鍪沁@類問(wèn)題最大的障礙强胰。
本文會(huì)將 LeetCode 里面的大部分滑動(dòng)窗口問(wèn)題分析舱沧、總結(jié)、分類哪廓，并提供一個(gè)可以參考的模版

問(wèn)題形式

滑動(dòng)窗口這類問(wèn)題一般需要用到雙指針來(lái)進(jìn)行求解狗唉，另外一類比較特殊則是需要用到特定的數(shù)據(jù)結(jié)構(gòu)，如 Map涡真，隊(duì)列等分俯。

題目問(wèn)法大致有這幾種

1. 給兩個(gè)字符串，一長(zhǎng)一短哆料，問(wèn)其中短的是否在長(zhǎng)的中滿足一定的條件存在

• 求長(zhǎng)的的最短子串缸剪，該子串必須涵蓋短的的所有字符
• 短串的某種排列在長(zhǎng)的中出現(xiàn)的所有位置

2. 給一個(gè)字符串或者數(shù)組，問(wèn)這個(gè)字符串的子串或者子數(shù)組是否滿足一定的條件

• 含有少于 k k k 個(gè)不同字符的最長(zhǎng)子串
• 所有字符都只出現(xiàn)一次的最長(zhǎng)子串

除此之外东亦，還有一些其他的問(wèn)法杏节，但是不變的是，這類題目脫離不開主串（主數(shù)組）和子串（子數(shù)組）的關(guān)系典阵，要求的時(shí)間復(fù)雜度往往是 O ( N ) O(N) O(N) 奋渔，空間復(fù)雜度往往是 O ( 1 ) O(1) O(1) 的。

解題思路與模板

根據(jù)前面的描述壮啊，滑動(dòng)窗口就是這類題目的重點(diǎn)嫉鲸，換句話說(shuō)，窗口的移動(dòng)就是重點(diǎn)歹啼！我們要控制前后指針的移動(dòng)來(lái)控制窗口玄渗，這樣的移動(dòng)是有條件的，也就是要想清楚在什么情況下移動(dòng)狸眼，在什么情況下保持不變藤树。
思路是保證右指針每次往前移動(dòng)一格，每次移動(dòng)都會(huì)有新的一個(gè)元素進(jìn)入窗口拓萌，這時(shí)條件可能就會(huì)發(fā)生改變岁钓，然后根據(jù)當(dāng)前條件來(lái)決定左指針是否移動(dòng)，以及移動(dòng)多少格。

/** 參考模板 */
slidingWindow(char[] s) {
    // 申請(qǐng)一個(gè)散列甜紫，用于記錄窗口中具體元素的個(gè)數(shù)情況
    // 這里用數(shù)組的形式呈現(xiàn)降宅，也可以考慮其他數(shù)據(jù)結(jié)構(gòu)
    int[] hash = new int[...];
    // 預(yù)處理（可省略）, 一般情況是初始化 hash 內(nèi)容
    ...
    // left 為窗口左指針，right 為窗口右指針
    // count 記錄題目要求記錄某些中間結(jié)果（最多最少等值）
    // result 記錄結(jié)果
    int left = 0, count = 0, result = 0;
    for (int right = 0; right < s.length; right++) {
        // 更新新元素在散列中的數(shù)量
        hash[s[right]]++;
        // 根據(jù)窗口的變更結(jié)果來(lái)改變條件值
        if (hash[s[right]] == ...) {
            count++;
        }
        // 如果當(dāng)前窗口條件不滿足囚霸，移動(dòng)左指針直至滿足窗口為止
        while (...) {           
            hash[s[left]]--;
            // 視情況改變記錄的中間結(jié)果
            if (...) {
                count--;
            }
            left++;
        }
        // 更新結(jié)果
        result = ...
    }
}

具體問(wèn)題

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

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

示例

輸入："abcabcbb"
輸出：3 
解釋：因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"拓型，所以其長(zhǎng)度為 3。

解題思路

輸入只有一個(gè)字符串瘸恼，要求子串里面不能夠有重復(fù)的元素劣挫，這里 count 都不需要定義，直接判斷哈希散列里面的元素是不是在窗口內(nèi)即可东帅，是的話得移動(dòng)左指針去重压固。
建立一個(gè) 128 位大小的整型數(shù)組，用來(lái)建立字符和其出現(xiàn)位置之間的映射靠闭。維護(hù)一個(gè)滑動(dòng)窗口帐我，窗口內(nèi)的都是沒(méi)有重復(fù)的字符，去盡可能的擴(kuò)大窗口的大小愧膀，窗口不停的向右滑動(dòng)拦键。

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.isEmpty()) return 0;
    char[] sArr = s.toCharArray();
    int[] hash = new int[128];
    int left = 0, result = Integer.MIN_VALUE;
    for (int right = 0; right < sArr.length; right++) {
        // 如果當(dāng)前遍歷到的字符從未出現(xiàn)過(guò)，那么直接擴(kuò)大右邊界
        hash[sArr[right]]++;
        // 如果當(dāng)前遍歷到的字符出現(xiàn)過(guò)檩淋，則縮小窗口（左指針向右移動(dòng)）
        while (hash[sArr[right]] != 1) {
            hash[sArr[left]]--;
            left++;
        }
        // 更新結(jié)果
        result = Math.max(result, right - left + 1);
    }
    return result;  
}

替換后的最長(zhǎng)重復(fù)字符

給你一個(gè)僅由大寫英文字母組成的字符串芬为，你可以將任意位置上的字符替換成另外的字符，總共可最多替換 k 次蟀悦。在執(zhí)行上述操作后媚朦，找到包含重復(fù)字母的最長(zhǎng)子串的長(zhǎng)度。

示例

輸入：s = "ABAB", k = 2
輸出：4
解釋：用兩個(gè)'A'替換為兩個(gè)'B',反之亦然日戈。

解題思路

最簡(jiǎn)單的方法就是把哈希散列遍歷一邊找到最大的字符數(shù)量询张，但是仔細(xì)想想如果我們每次新進(jìn)元素都更新這個(gè)最大數(shù)量，且只更新一次涎拉，我們保存的是當(dāng)前遍歷過(guò)的全局的最大值瑞侮，它肯定是比實(shí)際的最大值大的，我們左指針移動(dòng)的條件是 right - left + 1 - count > k鼓拧，保存的結(jié)果是 result = Math.max(result, right - left + 1)半火； 這里 count 比實(shí)際偏大的話，雖然導(dǎo)致左指針不能移動(dòng)季俩，但是不會(huì)記錄當(dāng)前的結(jié)果钮糖，所以最后的答案并不會(huì)受影響。

public int characterReplacement(String s, int k) {
    if (s == null || s.isEmpty()) return 0;
    char[] sArr = s.toCharArray();
    // 僅含大寫英文字母，設(shè)為26即可
    int[] hash = new int[26];
    // count記錄最大出現(xiàn)次數(shù)
    int left = 0, count = 0, result = 0;
    for (int right = 0; right < sArr.length; right++) {
        // 調(diào)整字母在hash中的索引位置
        hash[sArr[right] - 'A']++;
        // 比較最大數(shù)字符數(shù)和當(dāng)前字符的數(shù)量
        count = Math.max(count, hash[sArr[right] - 'A']);
        // 子字符串的長(zhǎng)度減去出現(xiàn)次數(shù)最多的字符個(gè)數(shù)大于k則移動(dòng)左指針
        while (right - left + 1 - count > k) {
            hash[sArr[left] - 'A']--;
            left++;
        }
        result = Math.max(result, right - left + 1);
    }
    return result;
}

長(zhǎng)度為 K 的無(wú)重復(fù)字符子串

給你一個(gè)字符串 S店归，找出所有長(zhǎng)度為 K 且不含重復(fù)字符的子串阎抒，請(qǐng)你返回全部滿足要求的子串的數(shù)目。

示例

輸入：S = "havefunonleetcode", K = 5
輸出：6
解釋：這里有 6 個(gè)滿足題意的子串消痛，分別是
'havef','avefu','vefun','efuno','etcod','tcode'

解題思路

根據(jù)題意我們發(fā)現(xiàn)相當(dāng)于窗口大小固定為K且叁，同時(shí)在窗口內(nèi)必須沒(méi)有重復(fù)的字符。我們用左右指針可以計(jì)算出當(dāng)前窗口的大小right - left + 1秩伞，同時(shí)再利用一個(gè)count對(duì)字符種類進(jìn)行計(jì)數(shù)（也可以直接用一個(gè)boolean值即可）逞带，那么很容易可以得出當(dāng)right - left + 1 > K 或者 count > 0時(shí)需要移動(dòng)左指針了。剩下的部分就是愉快地套用模板啦纱新。

public int numKLenSubstrNoRepeats(String S, int K) {
    if (S == null || S.length() < K) return 0;
    char[] sArr = S.toCharArray();
    int[] hash = new int[128];
    int left = 0, count = 0, result = 0;
    for (int right = 0; right < sArr.length; right++) {
        hash[sArr[right]]++;
        // 若更新hash后大于1展氓，說(shuō)明出現(xiàn)了重復(fù)種類的字符，count加1
        if (hash[sArr[right]] > 1) {
            count++;
        }
        // 當(dāng)子串超過(guò)窗口大小脸爱，或者窗口內(nèi)包含重復(fù)字符時(shí)遇汞，移動(dòng)左指針
        while (left < right && (right - left + 1 > K || count > 0)) {
            // 更新左指針右移后字符數(shù)量
            hash[sArr[left]]--;
            // 若更新后該字符數(shù)量仍大于0，說(shuō)明找到了重復(fù)的字符
            // 此時(shí)將count減1
            if (hash[sArr[left]] > 0) {
                count--;
            }
            left++;
        }
        // 更新結(jié)果簿废，此時(shí)子串剛好滿足窗口條件空入，結(jié)果加1，同時(shí)將count重置
        if (right - left + 1 == K) {
            result++;
            count = 0;
        }
    }
    return result;
}

至多包含兩個(gè)不同字符的最長(zhǎng)子串

給定一個(gè)字符串 s 捏鱼，找出至多包含兩個(gè)不同字符的最長(zhǎng)子串 t 执庐。

示例

輸入："ccaabbb"
輸出：5
解釋： t 是 "aabbb"，長(zhǎng)度為5

解題思路

類似于上一題导梆，不過(guò)我們用count來(lái)記錄當(dāng)前窗口內(nèi)字符的種類數(shù)量轨淌，當(dāng)出現(xiàn)新字符以及滑動(dòng)左指針時(shí)，做相應(yīng)的判斷來(lái)改變count看尼，窗口大小始終保持在滿足條件至多兩個(gè)不同字符的情況下递鹉。

 public int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s == null || s.isEmpty()) return 0;
    char[] sArr = s.toCharArray();
    int[] hash = new int[128];
    // count記錄出現(xiàn)過(guò)的不同種類字符的數(shù)量
    int left = 0, count = 0, result = Integer.MIN_VALUE;
    for (int right = 0; right < sArr.length; right++) {         
        hash[sArr[right]]++;
        // 若當(dāng)前字符在hash中計(jì)數(shù)為1，說(shuō)明是前面未出現(xiàn)過(guò)的藏斩，count加1       
        if (hash[sArr[right]] == 1) {
            count++;
        }
        // 若種類超過(guò)2了躏结，需要將左指針右移，以滿足窗口的條件
        while (count > 2) {
            // 更新左指針右移后字符數(shù)量
            hash[sArr[left]]--;
            // 若更新后該字符數(shù)量為0狰域，說(shuō)明當(dāng)前窗口只含有一個(gè)該類字符
            // 則種類數(shù)量count相應(yīng)要減1
            if (hash[sArr[left]] == 0) {
                count--;
            }
            left++;
        }
        // 更新結(jié)果
        result = Math.max(result, right - left + 1);
    }
    return result;
}

至多包含 K 個(gè)不同字符的最長(zhǎng)子串

給定一個(gè)字符串 s 媳拴，找出 至多 包含 k 個(gè)不同字符的最長(zhǎng)子串 T。

示例

輸入： s = "eceba", k = 2
輸出：3
解釋： 則 T 為 "ece"兆览，所以長(zhǎng)度為 3屈溉。

解題思路

和上一題完全一樣的思路，只需要把判斷窗口條件的地方改成 count > k 抬探，又一題困難被我們直接秒殺子巾。

public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s == null || s.isEmpty()) return 0;
    char[] sArr = s.toCharArray();
    int[] hash = new int[128];
    int left = 0, count = 0, result = Integer.MIN_VALUE;
    for (int right = 0; right < sArr.length; right++) {
        hash[sArr[right]]++;
        if (hash[sArr[right]] == 1) {
            count++;
        }
        // 此處改為超過(guò)k種不同字符則移動(dòng)左指針
        while (count > k) {
            hash[sArr[left]]--;
            if (hash[sArr[left]] == 0) {
                count--;
            }
            left++;
        }
        result = Math.max(result, right - left + 1);
    }
    return result;
}

下面來(lái)看看兩個(gè)字符串的情況

最小覆蓋子串

給你一個(gè)字符串 S、一個(gè)字符串 T，請(qǐng)?jiān)谧址?S 里面找出：包含 T 所有字母的最小子串线梗。

示例

輸入：S = "ADOBECODEBANC", T = "ABC"
輸出："BANC"
解釋：S 內(nèi)包含 T 中所有字母的最小子串為"BANC"

解題思路

同樣是兩個(gè)字符串之間的關(guān)系問(wèn)題椰于，因?yàn)轭}目求的最小子串，也就是窗口的最小長(zhǎng)度仪搔，說(shuō)明這里的窗口大小是可變的瘾婿，這里移動(dòng)左指針的條件變成，只要左指針指向不需要的字符僻造，就進(jìn)行移動(dòng)憋他。

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) return "";
    char[] sArr = s.toCharArray(), tArr = t.toCharArray();
    // 記錄字符出現(xiàn)次數(shù)
    int[] hash = new int[128];
    // 以T中的字符初始化hash內(nèi)字符數(shù)量
    for (char c : tArr) {
        hash[c]++;
    }
    // count 記錄匹配字符數(shù)，minLen 記錄最小子串長(zhǎng)度
    String result = "";
    int left = 0, count = 0, minLen = Integer.MAX_VALUE;
     for (int right = 0; right < sArr.length; right++) {
        // 更新S中字符在散列中的數(shù)量
        hash[sArr[right]]--;
        // 若經(jīng)過(guò)上一步減1后仍大于等于0
        // 說(shuō)明S中的該字符在T中出現(xiàn)過(guò)（因?yàn)槲覀冇肨中字符數(shù)量初始化了hash）髓削，匹配數(shù)加1
        if (hash[sArr[right]] >= 0) {
            count++;
        }
        // 若某字符在hash中為負(fù)，說(shuō)明在S中出現(xiàn)過(guò)镀娶，在T中未出現(xiàn)立膛，略過(guò)，不需要匹配
        while (left < right && hash[sArr[left]] < 0) {
            hash[sArr[left]]++;
            left++;
        }
        // 更新結(jié)果
        // count == tArr.length說(shuō)明找到了T中所有字符
        if (count == tArr.length && minLen > right - left + 1) {
            minLen = right - left + 1;
            result = s.substring(left, right + 1);
        }
     }
     return result;
}

字符串的排列

給定兩個(gè)字符串 s1 和 s2梯码，寫一個(gè)函數(shù)來(lái)判斷 s2 是否包含 s1 的排列宝泵。

示例

輸入：s1 = "ab" s2 = "eidbaooo"
輸出：True
解釋：s2 包含 s1 的排列之一 ("ba").

解題思路

首先窗口是固定的，窗口長(zhǎng)度就是s1的長(zhǎng)度轩娶，也就是說(shuō)儿奶，右指針移動(dòng)到某個(gè)位置后，左指針必須跟著一同移動(dòng)鳄抒，且每次移動(dòng)都是一格闯捎，count 用來(lái)記錄窗口內(nèi)滿足條件的元素，直到 count 和窗口長(zhǎng)度相等即可许溅。

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    char[] arr1 = s1.toCharArray(), arr2 = s2.toCharArray();
    int[] hash = new int[128];
    // 以s1中的字符初始化hash內(nèi)字符數(shù)量
    for (char c : arr1) {
        hash[c]++;
    }
    // count 記錄匹配字符數(shù)瓤鼻，size 表示窗口的大小
    int left = 0, count = 0, size = arr1.length;
    for (int right = 0; right < arr2.length; right++) {
        // 更新s2字符在散列中的數(shù)量
        hash[arr2[right]]--;
        // 說(shuō)明s2中的該字符在s1中出現(xiàn)過(guò)
        if (hash[arr2[right]] >= 0) {
            count++;
        }
        // 右指針移動(dòng)到超過(guò)窗口大小時(shí)，左指針跟著移動(dòng)
        if (right > size - 1) {
            hash[arr2[left]]++;
            // 若當(dāng)前是已經(jīng)匹配上的字符贤重，左移后會(huì)丟失匹配茬祷，故匹配數(shù)減1
            if (hash[arr2[left]] > 0) {
                count--;
            }           
            left++;         
        }
        // 更新結(jié)果，count == size 表示匹配字符滿足窗口大小
        if (count == size) {
            return true;
        }
    }
    return false;
}

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

給定一個(gè)字符串 s 和一個(gè)非空字符串 p并蝗，找到 s 中所有是 p 的字母異位詞的子串祭犯，返回這些子串的起始索引滚停。字符串只包含小寫英文字母，并且字符串 s 和 p 的長(zhǎng)度都不超過(guò) 20100陪每。

示例

輸入：s: "cbaebabacd" p: "abc"
輸出：[0, 6]
解釋：
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

解題思路

和上一題完全一致的思路檩禾，窗口固定為p串的長(zhǎng)度。

public List<Integer> findAnagrams(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) return new ArrayList<Integer>();
    char[] sArr = s.toCharArray(), tArr = t.toCharArray();
    // 僅含小寫英文字母饵婆，設(shè)為26即可
    int[] hash = new int[26];
    for (char c : tArr) {
        hash[c - 'a']++;
    }
    // count 記錄匹配字符數(shù)，size 表示窗口的大小
    int left = 0, count = 0, size = tArr.length;
    List<Integer> result = new ArrayList<>();
    for (int right = 0; right < sArr.length; right++) {
        // 更新s中的字符在散列中的數(shù)量
        hash[sArr[right] - 'a']--;
        // 說(shuō)明s中的該字符在t中出現(xiàn)過(guò)
        if (hash[sArr[right] - 'a'] >= 0) {
            count++;
        }
        if (right > size - 1) {
            hash[sArr[left] - 'a']++;
            if (hash[sArr[left] - 'a'] > 0) {
                count--;
            }
            left++;
        }
        // 更新結(jié)果戏售，記錄子串起始位置
        if (count == size) {
            result.add(left);
        }
    }
    return result;
}

最后來(lái)看看數(shù)組類型的題吧
最大連續(xù)1的個(gè)數(shù) III

給定一個(gè)由若干 0 和 1 組成的數(shù)組 A侨核，我們最多可以將 K 個(gè)值從 0 變成 1 灌灾。返回僅包含 1 的最長(zhǎng)（連續(xù)）子數(shù)組的長(zhǎng)度。

示例

輸入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
輸出：6
解釋：[1,1,1,0,0,1,1,1,1,1,1]

解題思路

這題有點(diǎn)像上面的 替換后的最長(zhǎng)重復(fù)字符些己，只不過(guò)把字符串換成了數(shù)組嘿般，由于只有兩種數(shù)字 0 和 1，并且只求連續(xù) 1 的長(zhǎng)度炉奴，我們可以連 hash 映射都不需要了瞻赶，直接計(jì)算遍歷到的 0 的個(gè)數(shù)即可。

public int longestOnes(int[] A, int K) {
    if (A == null) return 0;
    int left = 0, count = 0, result = 0;
    for (int right = 0; right < A.length; right++) {
        // 找到了0需要替換虑灰，count加1
        if (A[right] == 0) {
            count++;
        }
        while (count > K) {
            // 之前的0滑出了窗口痹兜，count減1
            if (A[left] == 0) {
                count--;
            }
            left++;
        }
        result = Math.max(result, right - left + 1);
    }
    return result;  
}

K 個(gè)不同整數(shù)的子數(shù)組

給定一個(gè)正整數(shù)數(shù)組 A字旭，如果 A 的某個(gè)子數(shù)組中不同整數(shù)的個(gè)數(shù)恰好為 K，則稱 A 的這個(gè)連續(xù)遗淳、不一定獨(dú)立的子數(shù)組為好子數(shù)組屈暗。

示例

輸入：A = [1,2,1,2,3], K = 2
輸出：7
解釋：恰好由 2 個(gè)不同整數(shù)組成的子數(shù)組
[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

解題思路

這題比較 tricky 的一個(gè)地方在于脂男，這里不是求最小值最大值种呐，而是要你計(jì)數(shù)爽室。
但是如果每次僅僅加 1 的話又不太對(duì)，例如 A = [1,2,1,2,3], K = 2 這個(gè)例子嘿架，假如右指針移到 index 為 3 的位置啸箫，如果按之前的思路左指針根據(jù) count 來(lái)移動(dòng)，當(dāng)前窗口是 [1,2,1,2]搜囱，但是怎么把 [2,1] 給考慮進(jìn)去呢柑土？
可以從數(shù)組和子數(shù)組的關(guān)系來(lái)思考绊汹！
假如 [1,2,1,2] 是符合條件的數(shù)組西乖，如果要計(jì)數(shù)的話，[1,2,1,2] 要求的結(jié)果是否和 [1,2,1] 的結(jié)果存在聯(lián)系薄腻？這兩個(gè)數(shù)組的區(qū)別在于多了一個(gè)新進(jìn)來(lái)的元素届案，之前子數(shù)組計(jì)數(shù)沒(méi)考慮到這個(gè)元素，假如把這個(gè)元素放到之前符合條件的子數(shù)組中組成的新數(shù)組也是符合條件的尽纽，我們看看這個(gè)例子中所有滿足條件的窗口以及對(duì)應(yīng)的滿足條件的子數(shù)組情況：

[1,2,1,2,3]   // 窗口滿足條件
 l r          // 滿足條件的子數(shù)組 [1,2]
[1,2,1,2,3]   // 窗口滿足條件
 l   r        // 滿足條件的子數(shù)組 [1,2],[2,1],[1,2,1]
[1,2,1,2,3]   // 窗口滿足條件
 l     r      // 滿足條件的子數(shù)組 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2]
[1,2,1,2,3]   // 窗口不滿足條件弄贿，移動(dòng)左指針至滿足條件
 l       r
[1,2,1,2,3]   // 窗口滿足條件
       l r    // 滿足條件的子數(shù)組 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2],[2,3]

你可以看到對(duì)于一段連續(xù)的數(shù)組矫膨，新的元素進(jìn)來(lái)期奔，窗口增加 1呐萌，每次的增量都會(huì)在前一次增量的基礎(chǔ)上加 1脚线。當(dāng)新的元素進(jìn)來(lái)打破當(dāng)前條件會(huì)使這個(gè)增量從新回到 1，這樣我們左指針移動(dòng)條件就是只要是移動(dòng)不會(huì)改變條件渠旁，就移動(dòng)船逮，不然就停止。

public int subarraysWithKDistinct(int[] A, int K) {
    if (A == null || A.length < K) return 0;
    // hash表示A中元素出現(xiàn)次數(shù)杂靶，因?yàn)闂l件中1 <= A[i] <= A.length        
    int[] hash = new int[A.length + 1]; 
    // kind表示出現(xiàn)過(guò)的元素種類
    // count表示子數(shù)組的計(jì)數(shù) 
    int left = 0, kind = 0, count = 1, result = 0;
    for (int right = 0; right < A.length; right++) {
        // 如果當(dāng)前遍歷到的元素從未出現(xiàn)過(guò)吗垮，那么直接擴(kuò)大右邊界
        hash[A[right]]++;
        // 當(dāng)前元素是第一次出現(xiàn)凹髓，種類加1
        if (hash[A[right]] == 1) {
            kind++;
        }
        // 左指針右移直至窗口滿足條件
        while (hash[A[left]] > 1 || kind > K) {
            hash[A[left]]--;
            if (kind > K) {
                count = 1;
                kind--; 
            } else {
                count++;
            }            
            left++;
        }        
        if (kind == K) {
            result += count;
        }
    }
    return result;
}

總結(jié)

至此蔚舀，本文用同一個(gè)框架解決了多道滑動(dòng)窗口的題目，這類問(wèn)題思維復(fù)雜度并不高赌躺，但是出錯(cuò)點(diǎn)往往在細(xì)節(jié)礼患。記憶常用的解題模版還是很有必要的，特別是對(duì)于這種變量名多咏瑟，容易混淆的題型痪署。有了這個(gè)框架，思考的點(diǎn)就轉(zhuǎn)化為 “什么條件下移動(dòng)左指針”余寥，無(wú)關(guān)信息少了，思考加實(shí)現(xiàn)自然不是問(wèn)題绪撵。