【基础算法精讲-学习记录】滑动窗口

视频学习记录

https://www.bilibili.com/video/BV1hd4y1r7Gq

• 滑动窗口是基于双指针的技巧，本质就是在维护左指针和右指针之间这个序列满足或不满足某种条件，一旦达到需要窗口需要变化的情况，就让左指针右移来缩小窗口。

例题和课后作业代码记录

209. 长度最小的子数组

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

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 另一种写法
        n = len(nums)
        ans = n + 1
        left = 0
        cur_sum = 0
        for right in range(n):
            cur_sum += nums[right]

            while cur_sum-nums[left] >= target:
                cur_sum -= nums[left]
                left += 1

            if cur_sum >= target and ans > right-left+1:
                # print(cur_sum, left, right)
                ans = right-left+1
        
        return ans if ans != n+1 else 0

        # 时间复杂度 On，空间复杂度O1
        n = len(nums)
        ans = n + 1
        left = 0
        cur_sum = 0
        for right in range(n):
            cur_sum += nums[right]
            while cur_sum >= target:
                ans = min(ans, right-left+1)
                cur_sum -= nums[left]
                left += 1
        
        return ans if ans != n+1 else 0

713. 乘积小于 K 的子数组

https://leetcode.cn/problems/subarray-product-less-than-k/description/

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # 时间 O（n），空间O1
        if k == 0 or k == 1:
            return 0 

        s = 1
        left = 0
        ans = 0
        for right, x in enumerate(nums):
            s *= x
            while s >= k:
                s /= nums[left]
                left += 1
            ans += right-left+1 
        
        return ans

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

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 时间复杂度On，空间复杂度由字符串的不重复字符数确定
        rec = set()
        ans = 0
        left = 0
        for right, x in enumerate(s):
            if x not in rec:
                rec.add(x)
                ans = max(ans, right-left+1)
            else:
                while s[left] != x:
                    rec.discard(s[left])
                    left += 1
                left += 1
        
        return ans

3090. 每个字符最多出现两次的最长子字符串

https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/description/

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        # 时间复杂度On，空间复杂度由字符串的不重复字符数确定
        rec = Counter()
        left = 0
        ans = 0
        for right, x in enumerate(s):
            rec[x] += 1
            while rec[x] > 2:
                rec[s[left]] -= 1
                left += 1
            ans = max(ans, right-left+1)
        return ans

2958. 最多 K 个重复元素的最长子数组

https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency/description/

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        # 时间复杂度On，空间复杂度由数组的不重复字符数确定
        rec = Counter()
        left = 0
        ans = 0
        for right, x in enumerate(nums):
            rec[x] += 1
            while rec[x] > k:
                rec[nums[left]] -= 1
                left += 1
            ans = max(ans, right-left+1)
        return ans

2730. 找到最长的半重复子字符串

https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/description/

class Solution:
    def longestSemiRepetitiveSubstring(self, s: str) -> int:
        # 时间复杂度On，空间复杂度O1
        # 虽说确实可以用哈希表来辅助，但是题目给了限定对数，那么为啥不直接维护这个对数呢
        ans = 0
        left = 0
        pair_count = 0
        for right, x in enumerate(s):
            if right > 0 and x == s[right-1]:
                pair_count += 1
            
            while pair_count > 1:
                if s[left]==s[left+1]:
                    pair_count -= 1
                left += 1
            
            ans = max(ans, right-left+1)

        return ans

1004. 最大连续1的个数 III

https://leetcode.cn/problems/max-consecutive-ones-iii/description/

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        # 能翻转k个0为1，换个角度就是求最长的连续1序列长度，其中最多可以包含两个0
        # 时间On，空间复杂度O1
        ans = 0
        left = 0
        zero_cnt = 0
        for right, x in enumerate(nums):
            if x == 0:
                zero_cnt += 1
            while zero_cnt > k:
                if nums[left] == 0:
                    zero_cnt -= 1
                left += 1
            ans = max(ans, right-left+1)
        return ans

2962. 统计最大元素出现至少 K 次的子数组

https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # 这题先是陷入到了之前的固定思维，想着怎么把这题转化为窗口内至多的题目，失败了
        # 看了灵神的思路解析才知道，完全可以窗口滑动到不满足后，left本身左边都符合
        # 时间 On，空间O1
        ans = 0
        max_num = max(nums)
        left = 0
        s = 0
        for x in nums:
            if x == max_num:
                s += 1

            while s >= k:
                if nums[left] == max_num:
                    s -= 1
                left += 1
            ans += left
        return ans
                

2302. 统计得分小于 K 的子数组数目

https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/description/

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # 时间On，空间复杂度O1
        ans = 0
        left = 0
        s = 0
        for right, x in enumerate(nums):
            s += x
            while s * (right-left+1) >= k:
                s -= nums[left]
                left += 1
            ans += right - left + 1
        return ans

1658. 将 x 减到 0 的最小操作数

https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums)-x
        if target < 0:
            return -1

        s = 0
        max_len = -1
        left = 0
        for right, x in enumerate(nums):
            s += x
            while s > target:
                s -= nums[left]
                left += 1
            if s == target:
                max_len = max(max_len, right - left + 1)
        return len(nums)-max_len if max_len >= 0 else -1

3795. 不同元素和至少为 K 的最短子数组长度

https://leetcode.cn/problems/minimum-subarray-length-with-distinct-sum-at-least-k/description/

class Solution:
    def minLength(self, nums: List[int], k: int) -> int:
        # 时间复杂度O（n），空间复杂度根据不重复的数字相关
        n = len(nums)
        ans = n + 1
        rec = defaultdict(int)
        left = 0
        s = 0
        for right, x in enumerate (nums):
            rec[x] += 1
            if rec[x] == 1:
                s += x
            while s>= k:
                ans = min(ans, right-left+1)
                rec[nums[left]] -= 1
                if rec[nums[left]] == 0:
                    s -= nums[left]
                left += 1

        return ans if ans <= n else -1

76. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 自己摸出的方法直接是灵神的优化版，还是挺有成就感的
        # 原始版本就是两个哈希表记录和比较，优化版就一个哈希表，记录差的字符，并用变量标记已经满足数量的字符数
        # 时间O（n），空间和t字符串中不重复的字符相关
        rec = defaultdict(int)
        enough_cnt = 0
        n = len(s)
        ans = "a"*100001

        for c in t:
            rec[c] += 1
        
        left = 0
        for right, x in enumerate(s):
            if x in rec:
                rec[x] -= 1
                if rec[x] == 0:
                    enough_cnt += 1
            
            while enough_cnt == len(rec):
                if len(ans) > right-left+1:
                    ans = s[left:right+1]
                out = s[left]
                if out in rec:
                    rec[out] += 1
                    if rec[out] == 1:
                        enough_cnt -= 1
                left += 1
            
        return ans if len(ans) <= 1e5 else ""