我們再來看幾題跟滑動窗口有關係的題目，基本上熟悉了框架，再問自己昨天的四大問題，得到答案很容易就得心應手了

字串排列

這題在leetcode的難度是Medium，題目如下

給定兩個字串 S與T ，請判斷S是否包含T的排列，也就是S的子字串中是否有T的某種全排列．

例如: S = “helloworld”，T=”oow”，則返回true，因為S中有一個子字串”owo”包含著T=”oow”的全排列．

思考一下，不大可能把T的全部組合排出來，再一個個去S裡面找，這樣太花時間了．

我們換成滑動視窗問題:”給定兩個字串S與T，請問S是否存在一個子字串，包含T的所有字元，且不包含其他字元？”

這樣一想，使用滑動視窗就簡單多了

注意昨天提到的四個問題 ，帶入框架中就能得到答案了

fun checkInclusion(t: String, s: String): Boolean {
    val need = HashMap<Char, Int>()
    t.forEach { need[it] = need.getOrDefault(it, 0) + 1 }
    val window = HashMap<Char, Int>()

    var left = 0
    var right = 0
    var valid = 0
    while (right < s.length) {
        val c = s[right]//c是即將進入視窗的字元
        right++
        if (need.containsKey(c)) {
            window[c] = window.getOrDefault(c, 0) + 1
            if (window[c] == need[c]) {
                valid++
            }
        }
    }
    while ((right - left) >= t.length) {
        if (valid == need.size) {//判斷答案，是否找到答案
            return true
        }
        val d = s[left]//d是即將離開視窗的字元
        left++
        if (need.containsKey(d)) {
            if (window[d] == need[d]) {
                valid--
            }
            window[d] = window.getOrDefault(d, 0) - 1
        }
    }
    return false
}

這題的解答基本跟昨天的最小覆蓋字串一樣，只是根據題目修改了兩個地方

1.當視窗需要開始縮小視窗的時機，是視窗大小大於目標字串t.length之時，因為題目要求排列沒有其他的字元混雜其中．

2.當發現valid == need.length時，說明現在在視窗的資料是一個合法的排列，所以立刻返回true．

找所有字母異位詞

這題在leetcode的難度也是Medium，題目如下：

給定一個字串S以及一個非空字串T，找到S中所有T的字母異位詞字串，並且返回這些字串的index

所謂的字母異位詞，就是全排列的意思．所以把這句話換句話說，就是這樣

找尋S之中T所有的排列，並且返回起始index

舉例來說:給一個字串S = “cbaebabacd”，T=”abc”，那麼會返回[0,6]，因為在起始索引0跟６開始後，便是子字串 “cba”與 “bac”，這兩個子字串都是T的排列

同樣的確認四個問題，帶入框架

fun findAnagrams(t: String, s: String): ArrayList<Int> {
    val need = HashMap<Char, Int>()
    t.forEach { need[it] = need.getOrDefault(it, 0) + 1 }
    val window = HashMap<Char, Int>()

    var left = 0
    var right = 0
    var valid = 0
    val ans = mutableListOf<Int>()

    while (right < s.length) {
        val c = s[right]
        right++
        if (need.containsKey(c)) {
            window[c] = window.getOrDefault(c, 0) + 1
            if (window[c] == need[c]) {
                valid++
            }
        }
        //判斷左側視窗是否要收縮
        //注意while迴圈的位置跟之前的問題不同了
        while ((right - left) >= t.length) {
            if (valid == need.size) {
                ans.add(left)
            }
            val d = s[left]
            left++
            if (need.containsKey(d)) {
                if (window[d] == need[d]) {
                    valid--
                }
                window[d] = window.getOrDefault(d, 0) - 1
            }
        }
    }

    return ans as ArrayList<Int>
}