滑動(dòng)窗口的定義：

滑動(dòng)窗口這一個(gè)技巧主要運(yùn)用于處理數(shù)組問題上，一般用于“子串”問題。精髓是，維護(hù)一個(gè)里面裝著元素的“窗口”，在將新元素裝進(jìn)“窗口”的同時(shí)，根據(jù)題意，把不符合題意的元素踢出“窗口”。

滑動(dòng)窗口的模板：

right:=0
left:=0
for right<len(數(shù)組或字符串){
  n = 數(shù)組[right]
  right+=1
  for (窗口需要收縮的時(shí)候，判斷){
    l = 數(shù)組[left]
    ...
    left+=1
  }
}

接下來看幾道題目：

Leetcode 209.長度最小的子數(shù)組

https://leetcode.cn/problems/minimum-size-subarray-sum/

題目簡介：找到長度最短的一個(gè)子數(shù)組。并且數(shù)組內(nèi)數(shù)字的和>=target

題目分析：窗口不斷擴(kuò)大，當(dāng)窗口里的元素的總和滿足條件后（>=target），窗口縮小，即target減去窗口左端的數(shù)。然后再用一個(gè)變量記錄窗口的大小，最小值隨時(shí)更新。直接用模板就好了：

func min(i, j int) int {
    if i >= j {
        return j
    } else {
        return i
    }
}
func minSubArrayLen(target int, nums []int) int {
    sum := 0
    right := 0
    left := 0
    res := 10000000
    for right < len(nums) {
        n := nums[right]
        right += 1
        sum += n
        for sum >= target {
            sum -= nums[left]
            res = min(res, right-left)
            left += 1
        }
    }
    if res == 10000000 {
        return 0
    }
    return res
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-805930.html

Leetcode 3.無重復(fù)的最長字串

給定一個(gè)字符串 s ，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

?

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

func lengthOfLongestSubstring(s string) int {
    right := 0
    left := 0
    res := 0
    check_dict := make(map[string]int)
    for right < len(s) {
        word := string(s[right])
        if _, exist := check_dict[word]; !exist {
            check_dict[word] = 1
        } else {
            check_dict[word] += 1
        }
        right += 1
        for check_dict[word] > 1 {
            l := string(s[left])
            left += 1
            check_dict[l] -= 1
        }
        if right-left > res {
            res = right - left
        }

    }
    return res

}

LEETCODE 904.水果成籃

https://leetcode.cn/problems/fruit-into-baskets/description/

題目有點(diǎn)拗口，簡單解釋：“窗口內(nèi)”只能含有兩種數(shù)字。問窗口最長能有多長？

可以用一個(gè)字典來裝元素。當(dāng)字典中出現(xiàn)3種及以上數(shù)字時(shí)，開始收縮窗口。有一個(gè)要點(diǎn)，當(dāng)元素的個(gè)數(shù)為“0”時(shí)，記得把鍵值對刪除。

func totalFruit(fruits []int) int {
    right := 0
    left := 0
    res := 0
    dict := make(map[int]int)
    for right < len(fruits) {
       n := fruits[right]
        right+=1
       if _, exist := dict[n]; !exist {
          dict[n] = 1
       } else {
          dict[n] += 1
       }
       for len(dict) > 2 {
          l := fruits[left]
          left += 1
          dict[l] -= 1
          if dict[l] == 0 {
                delete(dict,l)
          }
       }
        if right-left >res{
            res = right-left
        }
    }
    return res
}

?

?

到了這里，關(guān)于Leetcode with Golang 滑動(dòng)窗口 Part1的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！