滑动窗口高频面试题｜最长无重复子串、最小子数组

前言

滑动窗口是字符串、子数组题型万能解法，双指针动态调节窗口大小，时间效率极高，笔试面试出场率拉满。本篇汇总经典题型，思路 + 可直接默写 Python 代码，吃透这类题直接秒解。

一、滑动窗口核心思想

1. 用左右双指针围成一个窗口
2. 右指针不断向右扩张，满足条件停止
3. 不满足条件则移动左指针收缩窗口
4. 全程只遍历一遍数组 / 字符串，时间复杂度 O (n)
5. 分为：固定窗口大小、可变窗口大小两大类

二、经典高频手撕题

1. 最长无重复字符子串（超级高频）

题意：找出字符串中不含重复字符的最长子串长度

def lengthOfLongestSubstring(s): win = set() left = 0 res = 0 for right in range(len(s)): # 出现重复，左指针右移缩窗口 while s[right] in win: win.remove(s[left]) left += 1 win.add(s[right]) res = max(res, right - left + 1) return res

2. 长度最小的子数组

题意：给定目标和，找数组中和 ≥ target 的最短连续子数组长度

def minSubArrayLen(target, nums): left = 0 cur_sum = 0 res = float('inf') for right in range(len(nums))