Algorithms training - Sliding window algorithm. 算法训练(一) 滑动窗口.

讲起滑动窗口呢, 最紧要就系套模板, 优点系可以将 O(n^2) 或更高时间复杂度降低到 O(n).
呢个系在 csdn 上抄落来嘅, 仅供参考: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是等值子数组

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

输入：nums = [1,3,2,3,1,3], k = 3

输出：3

解释：最优的方案是删除下标 2 和下标 4 的元素。 删除后，nums 等于 [1, 3, 3, 3] 。 最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。 可以证明无法创建更长的等值子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import Counter

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        left = 0
        right = 0
        res = -1
        n = len(nums)
        mp = Counter()
        max_fre = 0 # 历史最大长度

        while right < n:
            mp[nums[right]]+=1
            max_fre = max(max_fre, mp[nums[right]])

            while ((right - left + 1) - max_fre > k):
                mp[nums[left]]-=1
                left+=1
            
            res = max(res, max_fre)
            right += 1

        return res