企业官网建设流程全解析

3. 无重复字符的最长子串
   一、题目描述
   给定一个字符串 s ，找出其中不含有重复字符的最长子串的长度。
   ⚠️ 重点区分：

• 子串：连续的一段字符（本题要求）
• 子序列：可以不连续（不算）
  示例：
• 输入：s = “abcabcbb” 输出：3（最长无重复子串为 abc/bca/cab）
• 输入：s = “bbbbb” 输出：1
• 输入：s = “pwwkew” 输出：3（wke/kew，pwke 是子序列，不合法）
  数据范围：0 <= s.length <= 10^5，必须保证 O(n) 时间复杂度，暴力枚举会超时。
  二、解题核心思路：滑动窗口（双指针）
  本题是滑动窗口经典模板题，核心思想：用左右指针维护一个窗口 [left, right]，窗口内始终保持「无重复字符」。
  窗口规则

1. 右指针 right 不断向右扩张，遍历所有字符；
2. 当新字符出现重复时，不断右移左指针 left，收缩窗口，直到窗口无重复；
3. 每次遍历更新窗口最大长度，遍历结束即为答案。
   三、解法一：哈希集合实现（易懂、新手首选）
   思路说明
   使用 unordered_set 存储当前窗口内的所有字符，快速判断字符是否重复：

• 右指针字符不在集合中：直接加入集合，更新最大长度；

• 右指针字符在集合中：说明重复，删除左指针字符、左指针右移，直到无重复。
  完整AC代码（C++）
  class Solution {
  public:
  int lengthOfLongestSubstring(string s) {
  // 存储当前窗口内的字符
  unordered_set st;
  int left = 0;
  int maxLen = 0;

  for (int right = 0; right < s.size(); right++) { // 出现重复字符，收缩左窗口 while (st.find(s[right]) != st.end()) { st.erase(s[left]); left++; } // 加入当前字符，扩张右窗口 st.insert(s[right]); // 更新最大长度 maxLen = max(maxLen, right - left + 1); } return maxLen;

  }
  };
  

四、解法二：数组记录位置（面试最优、速度最快）
由于题目字符包含：字母、数字、符号、空格，ASCII 码范围 0~127。我们可以用固定数组替代哈希集合，避免哈希冲突、查询更快，是面试满分最优解。
思路优化
数组 pos[128] 记录每个字符最后出现的下标，初始值为 -1：

1. 如果当前字符上次出现的下标 ≥ left，说明在窗口内重复，直接更新左边界；

2. 更新当前字符的最新下标；

3. 实时更新最长子串长度。
   完整AC代码（最优解）
   class Solution {
   public:
   int lengthOfLongestSubstring(string s) {
   // ASCII字符共128个，初始化为-1（未出现）
   vector pos(128, -1);
   int maxLen = 0;
   int left = 0;

   for (int right = 0; right < s.size(); right++) { // 字符在当前窗口重复，更新左边界 if (pos[s[right]] >= left) { left = pos[s[right]] + 1; } // 更新字符最新位置 pos[s[right]] = right; // 统计最大长度 maxLen = max(maxLen, right - left + 1); } return maxLen;

   }
   };
   五、复杂度分析
   解法一（哈希集合）

• 时间复杂度：O(n)，左右指针最多各遍历一次字符串
• 空间复杂度：O(1)，字符种类有限，集合最大存储128个字符
  解法二（数组优化）
• 时间复杂度：O(n)，一次遍历，无冗余操作
• 空间复杂度：O(1)，固定128长度数组，常数空间
• 优势：比哈希表更快，无哈希查找开销，适配1e5大数据量
  六、常见易错点总结

1. 混淆子串和子序列：必须连续，不能跳过字符；
2. 左指针不能回退：滑动窗口左指针只增不减，保证O(n)复杂度；
3. 初始化问题：位置数组必须初始为-1，不能是0（字符串下标从0开始）；
4. 空字符串处理：代码天然兼容空串，直接返回0，无需特判。
   七、模板总结
   无重复最长子串是滑动窗口经典模板，适用于：最长无重复、最长满足条件子串、最小覆盖子串等系列题目，核心套路：
   右指针扩张，条件不满足时左指针收缩，实时更新答案