滑动窗口

[TOC]

Leetcode刷题

3. 无重复字符的最长子串

// ==========  解法  最为容易理解的一种做法。 ===============

// 左指针代表枚举子串的起始位置
// 右指针表示不包干重复字符串的最长子串的结束位置
func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符是否出现过
    m := map[byte]int{}
    n := len(s)
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    right, ans := -1, 0
    for left := 0; left < n; left++ {
        if left != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[left-1])
        }
        for right+1 < n && m[s[right+1]] == 0 { // 这里意思就是一直挪动右指针，到一个没有重复的时候停下来。
            m[s[right+1]]++
            right++
        }
        // 第 left 到 right 个字符是一个极长的无重复字符子串
        ans = max(ans, right-left+1)
    }
    return ans
}

//  解法 ，最合适的一种解法，一定要记住
func lengthOfLongestSubstring(s string) int {
    len_s := len(s)
    if len_s == 0 {
        return 0
    }
    tempMap := make(map[byte]int)
    j := 0
    res := 0
    for i := 0; i < len_s; i++ {
        if _, ok := tempMap[s[i]]; ok { // 判断这个key在不在这个map中
            j = max(j, tempMap[s[i]]+1) // 这一步非常关键，为了针对 abba 这种场景。
        }
        tempMap[s[i]] = i
        res = max(res, i-j+1)

    }
    return res
}

159. 至多包含两个不同字符的最长子串 【会员/中等/滑动窗口】

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。

输入: "eceba"

输出: 3

解释: t 是 "ece"，长度为3。

输入: "ccaabbb"

输出: 5

解释: t 是 "aabbb"，长度为5。

// ====================  解法二  窗口移动，个人推荐解法二，删除map中多余的，维持map 大小=======================
func lengthOfLongestSubstringTwoDistinct(s string) int {
    if len(s) <= 2 {
        return len(s)
    }
    left, right := 0, 0 // 左右移动指针
    maxLen := 0
    tempMap := make(map[byte]int)
    for ; right < len(s); right++ { // 也就是右指针一直在往右边移动，左边指针只有在字符种类大于二的时候才移动

        tempMap[s[right]]++

        for len(tempMap) > 2 {
            tempMap[s[left]]--
            if tempMap[s[left]] == 0 {
                delete(tempMap, s[left])
            }
            left++
        }
        maxLen = maxNum(maxLen, right-left+1)

    }
    return maxLen

}

340. 至多包含 K 个不同字符的最长子串【会员/中等/滑动窗口】

// ========  解法二  窗口移动，个人推荐解法二，删除map中多余的，维持map 大小=======================
func lengthOfLongestSubstringKDistinct(s string, k int) int {
    if len(s) <= k {
        return len(s)
    }

    left, right := 0, 0 // 左右移动指针
    maxLen := 0
    tempMap := make(map[byte]int)
    for ; right < len(s); right++ { // 也就是右指针一直在往右边移动，左边指针只有在字符种类大于二的时候才移动

        tempMap[s[right]]++

        for len(tempMap) > k {
            tempMap[s[left]]--
            if tempMap[s[left]] == 0 {
                delete(tempMap, s[left])
            }
            left++
        }
        maxLen = maxNum(maxLen, right-left+1)

    }
    return maxLen

}

395. 至少有 K 个重复字符的最长子串【中等】

1100. 长度为 K 的无重复字符子串【会员/中等】

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。

输入：S = "havefunonleetcode", K = 5

输出：6

解释：这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。

输入：S = "home", K = 5

输出：0

解释：注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。

// ============== 解法一  推荐这种解法，一定要会 =====
func numKLenSubstrNoRepeats(s string, k int) int {
    len_s := len(s)
    if len_s < k {
        return 0
    }

    count := 0
    left, right := 0, 0
    tempMap := make(map[byte]int)
    for ; right < len_s; right++ {
        tempMap[s[right]]++
        for tempMap[s[right]] > 1 {
            tempMap[s[left]]--
            if tempMap[s[left]] == 0 {
                delete(tempMap, s[left])
            }
            left++
        }

        if len(tempMap) == k {
            count++
            delete(tempMap, s[left])
            left++
        }
    }
    return count
}

487. 最大连续1的个数 II【会员/中等】

给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

输入：nums = [1,0,1,1,0]

输出：4

解释：翻转第一个 0 可以得到最长的连续 1。 当翻转以后，最大连续 1 的个数为 4。

输入：nums = [1,0,1,1,0,1]

输出：4

func findMaxConsecutiveOnes(nums []int) int {
    left, right := 0, 0
    zero_pos := -1
    res := 0
    for right = 0; right < len(nums); right++ {
        if nums[right] == 0 {
            if zero_pos != -1 {     //  这一块很关键
                left = zero_pos + 1
            }
            zero_pos = right
        }
        res = max(res, right-left+1)
    }
    return res
}

1004. 最大连续1的个数 III【中等】

// =============== 解法二  滑动窗口内最多有 K 个 00，求滑动窗口最大的长度，这种做法最好，是需要牢记的 =============
func longestOnes(A []int, K int) int {
    left := 0
    res := 0
    count := 0

    for right := 0; right < len(A); right++ {
        if A[right] == 0 {
            count++
        }
        for count > K {
            if A[left] == 0 { //逐渐移动左指针
                count--
            }
            left++
        }
        res = max(res, right-left+1)
    }
    return res
}

209. 长度最小的子数组【中等】

// 我们用 2 个指针，一个指向数组开始的位置，一个指向数组最后的位置，并维护区间内的和 sum 大于等于 ss 同时数组长度最小。
func minSubArrayLen(target int, nums []int) int {

    len_num := len(nums)
    if len_num == 0 {
        return 0
    }

    minValue := math.MaxInt32

    sum := 0
    left, right := 0, 0
    for ; right < len_num; right++ {
        sum += nums[right]
        for sum >= target {
            minValue = min(minValue, right-left+1)
            sum -= nums[left]
            left++
        }
    }
    if minValue == math.MaxInt32 { // 这里比较关键，1, 1, 1, 1, 1, 1, 1  就是所有和加一起，都小于target
        return 0
    }
    return minValue

}

1151. 最少交换次数来组合所有的 1 【会员/中等】

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

输入: data = [1,0,1,0,1]

输出: 1

解释:

有三种可能的方法可以把所有的 1 组合在一起：

[1,1,1,0,0]，交换 1 次；

[0,1,1,1,0]，交换 2 次；

[0,0,1,1,1]，交换 1 次。

所以最少的交换次数为 1。

输入：data = [0,0,0,1,0]

输出：0

解释：

由于数组中只有一个 1，所以不需要交换。

输入：data = [1,0,1,0,1,0,0,1,1,0,1]

输出：3

解释：

交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]

输出: 8

1208. 尽可能使字符串相等【中等】

424. 替换后的最长重复字符 （中等/滑动窗口）

76. 最小覆盖子串（困难/滑动窗口）

// https://leetcode.cn/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/ 看这里的图解释
// https://leetcode.cn/problems/minimum-window-substring/solution/golangshuang-zhi-zhen-dan-ha-xi-biao-by-8cn0r/

func minWindow(s string, t string) string {
    tempT := make(map[byte]int)
    for i := range t {
        tempT[t[i]]++
    }
    res := ""
    left, right := 0, 0
    minLen := math.MaxInt32
    tempS := make(map[byte]int)
    for ; right < len(s); right++ {
        tempS[s[right]]++
        for isContain(tempT, tempS) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                res = s[left : right+1]
            }
            tempS[s[left]]--
            left++
        }
    }
    return res
}

func isContain(tempT map[byte]int, tempS map[byte]int) bool {
    for i := range tempT {
        if tempS[i] < tempT[i] {
            return false
        }
    }
    return true
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

992. K 个不同整数的子数组 (困难/滑动窗口)

1248. 统计「优美子数组」 (中等/滑动窗口)

1852. 每个子数组的数字种类数 (会员/中等/滑动窗口)

给你一个整数数组 nums与一个整数 k，请你构造一个长度 n-k+1 的数组 ans，这个数组第i个元素 ans[i] 是每个长度为k的子数组 nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]]中数字的种类数。

返回这个数组 ans。


输入: nums = [1,2,3,2,2,1,3], k = 3
输出: [3,2,2,2,3]
解释：每个子数组的数字种类计算方法如下：
- nums[0:2] = [1,2,3] 所以 ans[0] = 3
- nums[1:3] = [2,3,2] 所以 ans[1] = 2
- nums[2:4] = [3,2,2] 所以 ans[2] = 2
- nums[3:5] = [2,2,1] 所以 ans[3] = 2
- nums[4:6] = [2,1,3] 所以 ans[4] = 3

输入: nums = [1,1,1,1,2,3,4], k = 4
输出: [1,2,3,4]
解释: 每个子数组的数字种类计算方法如下：
- nums[0:3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1:4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2:5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3:6] = [1,2,3,4] 所以 ans[3] = 4

1918. 第 K 小的子数组和·（会员/中等/滑动窗口+二分查找）

给你一个 长度为 n 的整型数组 nums 和一个数值 k ，返回 第 k 小的子数组和。

子数组 是指数组中一个 非空 且不间断的子序列。  子数组和 则指子数组中所有元素的和。

输入: nums = [2,1,3], k = 4
输出: 3
解释: [2,1,3] 的子数组为：
- [2] 和为 2
- [1] 和为 1
- [3] 和为 3
- [2,1] 和为 3
- [1,3] 和为 4
- [2,1,3] 和为 6 
最小子数组和的升序排序为 1, 2, 3, 3, 4, 6。 第 4 小的子数组和为 3 。

输入：nums = [3,3,5,5], k = 7
输出：10
解释：[3,3,5,5] 的子数组为：
- [3] 和为 3
- [3] 和为 3
- [5] 和为 5
- [5] 和为 5
- [3,3] 和为 6
- [3,5] 和为 8
- [5,5] 和为 10
- [3,3,5], 和为 11
- [3,5,5] 和为 13
- [3,3,5,5] 和为 16
最小子数组和的升序排序为 3, 3, 5, 5, 6, 8, 10, 11, 13, 16。第 7 小的子数组和为 10 。