【小白笔记】无重复字符的最长子串和长度最小的子数组（滑动窗口中两种不同的“窗口控制策略）

这个问题是“滑动窗口 (Sliding Window)”算法的顶级经典题。

在处理“最长子串”、“子数组”等问题时，滑动窗口能够将复杂度从O(N2)O(N^2)O(N2)降低到O(N)O(N)O(N)。

1. 核心思路：滑动窗口

想象字符串上有一个可以伸缩的窗口：

1. 右边界 (right)不断向右移动，把字符纳入窗口。
2. 检查重复：如果新加入的字符已经在窗口里了，说明窗口不合法了。
3. 左边界 (left)被迫向右收缩，直到把那个重复的字符“踢出去”为止。
4. 记录最大值：在窗口合法的每一步，记录窗口的长度（right - left + 1），取最大值。

2. 优化工具：哈希表 (Map/Dict)

为了快速知道某个字符是否在窗口内，以及它在什么位置，我们使用一个哈希表来记录：

• Key: 字符本身。
• Value: 该字符最近一次出现的索引位置。

3. 代码实现 (Python)

classSolution:deflengthOfLongestSubstring(self,s:str)->int:# 哈希表记录字符最后出现的位置char_map={}left=0max_len=0forrightinrange(len(s)):char=s[right]# 如果当前字符已经在哈希表中，且它的索引在窗口内ifcharinchar_mapandchar_map[char]>=left:# 关键：左边界直接跳到重复字符上次出现的下一个位置left=char_map[char]+1# 更新/记录当前字符的最新位置char_map[char]=right# 计算当前窗口长度并更新最大值max_len=max(max_len,right-left+1)returnmax_len

4. 为什么left能够“直接跳跃”？

假设字符串是a b c d b e f，当right走到第二个b时：

• 窗口内是a b c d。
• 新来的b和索引为1的b重复了。
• 我们不需要把left一步步挪。我们知道，只要left还在索引1及其左边，窗口就永远包含两个b。
• 所以，left直接跳到1 + 1 = 2的位置（即字符c），窗口瞬间变合法。

5. 复杂度分析

• 时间复杂度:O(N)O(N)O(N)。虽然有for循环，但left和right都只是一路向右，没有回退。
• 空间复杂度:O(min(M,N))O(min(M, N))O(min(M,N))。NNN是字符串长度，MMM是字符集的大小（比如 ASCII 码只有 128 个）。

总结：滑动窗口的“模版”

这种题通常遵循一个套路：

1. 进：右指针进位，加入新元素。
2. 判：判断当前窗口是否满足条件（本题是判断重复）。
3. 出：如果不满足，左指针出位，直到满足为止。
4. 算：在窗口合法时更新结果。

这个问题紧接着“最长子串”的逻辑，但目标相反：这次我们要找的是满足条件的“最短”连续区间。

这依然是滑动窗口的经典应用，但窗口的收缩时机发生了变化。

1. 核心思路：动态窗口（“进”与“缩”）

想象你手里拿着一个弹簧：

1. 右边界right负责“伸”：不断把数字加入窗口，直到窗口内的总和sum >= target。
2. 左边界left负责“缩”：一旦总和达标，说明我们找到了一个可行解。但为了找“最小”长度，我们要尝试从左侧缩减窗口，看看在总和依然达标的前提下，能不能让窗口更短。
3. 更新结果：在每次缩小窗口的过程中，记录最小的窗口长度。

2. 代码实现 (Python)

classSolution:defminSubArrayLen(self,target:int,nums:List[int])->int:n=len(nums)left=0current_sum=0# 初始化为一个不可能达到的大值min_len=float('inf')forrightinrange(n):# 1. 右指针进位，增加总和current_sum+=nums[right]# 2. 只要当前和满足条件，就开始尝试收缩左边界whilecurrent_sum>=target:# 更新最小长度 (当前窗口长度为 right - left + 1)min_len=min(min_len,right-left+1)# 尝试从左边踢出一个数，看看剩下的还够不够current_sum-=nums[left]left+=1# 3. 如果 min_len 没变过，说明没找到满足条件的子数组return0ifmin_len==float('inf')elsemin_len

3. 为什么这个逻辑能行？（关键点）

• 为什么用while而不是if？
  因为在剔除左边的一个数后，剩下的和可能依然大于等于target。我们需要一直缩，直到和变得小于target为止，这样才能确保我们不漏掉任何一个可能的最小长度。
• 为什么不需要回头看？
  因为数组里的数都是正整数。右移left必然会让和变小，右移right必然会让和变大。这种单调性保证了滑动窗口的有效性。

4. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)。
  虽然代码里有for循环嵌套while循环，但仔细观察：每个元素最多被right访问一次，最多被left访问一次。整个过程就像两只虫子在爬，每个指针都只走了一遍数组。
• 空间复杂度：O(1)O(1)O(1)。只用了几个变量。

总结：滑动窗口的“伸缩”哲学

• 求最长：右指针主动移，左指针被动跟（发现不合规才动）。
• 求最短：右指针主动移，左指针主动追（只要合规就拼命缩，直到不合规）。

进阶思考

这道题能用滑动窗口的前提是：数组中全是正整数。
如果数组中包含负数，窗口的和就不再具有“右移必大，左移必小”的单调性了。那种情况下，我们需要用到另一种技术——前缀和 + 哈希表。
这是一个非常敏锐的观察！你指出的其实是滑动窗口中两种不同的“窗口控制策略”。

虽然两道题整体都是O(N)O(N)O(N)，但因为问题的**性质（求最长 vs 求最短）**不同，导致左指针（left）的移动逻辑完全不同。

1. 无重复最长子串（求最长）：if逻辑（或单次跳跃）

在求最长时，我们是在**“发现不合规时，被迫移动一次左指针”**。

• 逻辑：窗口一直向右扩展，直到新来的字符造成了重复。
• 动作：此时我们只需要把left移动到重复字符上次出现的下一个位置。这个动作是一次性的。
• 代码体现：

  ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1# 瞬间跳过去，不需要循环

  即便不使用哈希表记录位置，而是用while剔除，它也只是为了恢复合规。一旦合规，我们就停止移动left，继续增加right来追求“更长”。

2. 长度最小子数组（求最短）：while逻辑

在求最短时，我们是在**“只要合规，就拼命压榨左指针”**。

• 逻辑：当窗口和满足sum >= target时，这只是一个“可行解”。为了找到“最优解（最短）”，我们要看看缩掉左边一个数后，是不是依然合规。
• 动作：
  1. 合规了？记录长度，删掉左边的，再看看还合规吗？
  2. 还合规？再记录长度，再删掉左边的…
     这个过程必须用while，因为你可能可以连续删掉好几个数字，窗口依然满足条件。
• 代码体现：

  whilecurrent_sum>=target:min_len=min(min_len,right-left+1)# 记录current_sum-=nums[left]# 尝试缩小left+=1# 循环继续

3. 核心差异对比

总结

• 最长子串：右指针是“先锋”，左指针是“底线”。只有底线被触碰了（重复），左指针才动。
• 最短数组：右指针是“补给”，左指针是“追求”。补给一够（达标），左指针就立刻出发去寻找更短的可能。

如果你把“最短数组”里的while改成if，你就会漏掉很多情况。比如target=7, nums=[1,1,1,1,7]，当right走到7时，和变成了11。用if你只能缩短一次变成[1,1,1,7]，而用while它可以一路缩到只剩[7]，这才是真正的最短。