滑动窗口
2022-02-18 本文已影响0人
Eden0503
[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 。
