LeetCode热榜百题Python版子串解法

一、560. 和为 K 的子数组

思路：

这是一道典型运用前缀和概念来解决的题目。通过构建前缀和数组，利用前缀和之间的差值来快速判断子数组的和是否符合要求。

代码：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        presum = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            presum[i + 1] = presum[i] + x  # 构造长度为n+1的前缀和序列

        ans = 0
        from collections import defaultdict
        cnt = defaultdict(int)
        for p in presum:
            ans += cnt[p - k]
            cnt[p] += 1
        return ans

二、239. 滑动窗口最大值

思路1：暴力解法

直接按照题目要求进行暴力求解，通过遍历滑动窗口内的元素来找到最大值。不过这种方法的时间复杂度较高，为 O(n²)。具体来说，设定窗口的左右边界，不断移动窗口并计算当前窗口内的最大值。

代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == 1:
            return nums
        res = []
        left, right = 0, k
        while left <= (len(nums) - k):
            res.append(max(nums[left:right]))
            left += 1
            right += 1
        return res

思路2：单调队列

使用单调队列来优化求解过程，主要分为三步：
1. 入队：将元素加入队尾，并维护队列的单调性（这里为了找最大值，保持单调递减）。
2. 出队：当队列首元素超出滑动窗口范围时，将其从队首移除。
3. 记录结果：当窗口形成一定大小后，记录当前窗口的最大值。

代码：

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            # 维护队列单调性，保证队列为单调递减
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)

            # 检查队首是否超出窗口范围，超出则移除
            if i - q[0] >= k:
                q.popleft()

            # 当窗口形成后，记录当前最大值
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

三、76. 最小覆盖子串

思路：

可以利用Counter来进行比较操作，通过维护两个计数器分别统计当前窗口内的字符出现情况和目标子串的字符出现情况，然后通过移动窗口的左右边界来找到最小覆盖子串。

代码：

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        ansLeft, ansRight = -1, len(s)
        cntS = Counter()
        cntT = Counter(t)

        left = 0
        for right, word in enumerate(s):
            cntS[word] += 1
            # 当当前窗口包含目标子串时，尝试缩小左边界
            while cntS >= cntT:
                if right - left < ansRight - ansLeft:
                    ansLeft, ansRight = left, right
                cntS[s[left]] -= 1
                left += 1
        return "" if ansLeft < 0 else s[ansLeft:ansRight+1]