行业资讯
LeetCode 第3题《无重复字符的最长子串》笔记
一、题目回顾题目给定一个字符串s找出其中不含有重复字符的最长子串的长度。示例输入s abcabcbb输出3解释因为无重复字符的最长子串是abc所以长度为 3。提示0 s.length 5 * 10^4s由英文字母、数字、符号和空格组成二、核心知识点知识点1滑动窗口的核心思想滑动窗口是处理子串问题的经典方法用两个指针左、右维护一个动态窗口。右指针 (right)负责向右扩展将新字符加入窗口。左指针 (left)负责在发现重复时将窗口左侧收缩到重复字符之后。核心目标始终保证窗口内所有字符不重复并记录窗口长度的最大值。形象理解想象一个可以伸缩的“窗口”在字符串上滑动右边界不断尝试扩大左边界在遇到重复时向右收缩。知识点2关键数据结构last_pos数组作用快速查询一个字符是否在窗口内以及它上一次出现的位置。定义int last_pos[128];存储逻辑下标字符的 ASCII 码值例如a的 ASCII 码是 97。值该字符最后一次出现的位置索引。初始值设为-1表示该字符从未出现。为何固定128足以覆盖所有标准 ASCII 字符空间开销极小512字节。图解存储结构字符: a b c d e ... z ASCII: 97 98 99 100 101 ... 122 last_pos数组 索引: 0 1 2 ... 97 98 99 100 ... 127 [ ][ ][ ] [3 ][5 ][2 ][-1 ] [ ] 不 不 不 a b c d 用 用 用 的 的 的 的 值 值 值 值知识点3核心判断逻辑last_pos[ch] left问题为什么这一句就能判断字符ch是否重复解答它判断的是字符ch上一次出现的位置是否在当前窗口内。last_pos[ch]字符ch上一次出现的位置。left当前窗口的左边界。当前窗口范围是[left, right]。判断逻辑若last_pos[ch] left→ 该字符的上次出现位置在窗口内 →重复若last_pos[ch] left→ 该字符的上次出现位置已被移出窗口 →不重复可以安全加入。图解三种情况情况1字符在窗口内重复字符串: a b c a b 索引: 0 1 2 3 4 [窗口] left1, right3 要加入 right4 的 b last_pos[b] 1 (在索引1) 判断1 left(1)? 是✅ → 重复了情况2字符不在窗口内不重复字符串: a b c a b 索引: 0 1 2 3 4 [窗口] left2, right3 要加入 right4 的 b last_pos[b] 1 (在索引1) 判断1 left(2)? 否❌ → 没重复知识点4窗口滑动操作处理重复的步骤当遇到重复字符ch时执行以下三步移动左指针left last_pos[ch] 1;直接跳到重复字符的下一个位置保证新窗口无重复。更新位置last_pos[ch] right;将ch的最新位置更新为当前位置。更新最大长度max_len max(max_len, right - left 1);图解执行过程以s abcabcbb为例第4步right3, cha, last_pos[a]0, left0 发现重复left从0跳到1 窗口从 [a,b,c] 变为 [b,c,a] 第5步right4, chb, last_pos[b]1, left1 发现重复left从1跳到2 窗口从 [b,c,a] 变为 [c,a,b]知识点5为什么你的初步想法需要修正你的初步想法“从第一个开始遇到重复就截止然后从这个重复出现的最后一个开始接着计数。”问题与修正这个想法接近滑动窗口但移动方式有误。不应从“重复的最后一个”开始而应从重复字符第一次出现位置的下一个位置开始即left last_pos[ch] 1。这样才能保证新窗口内不再包含重复字符。举例说明s abca 正确做法遇到第二个a时left从0跳到1窗口变为 [b,c,a] 你的做法从第二个a开始窗口为 [a]漏掉了 [b,c,a]三、常见错误总结错误1只检查相邻字符错误写法if (s[i] s[i-1])问题分析只能发现像aa这种紧挨着的重复无法发现abca中相距较远的重复字符a。正确做法必须用last_pos数组检查所有出现过的字符判断其是否在当前窗口内。错误2左指针移动方式错误错误写法left;一次只移动一位问题分析窗口内可能仍然存在其他重复字符效率低且容易出错。例如abcb中遇到第二个b时left应跳到2而不是1。正确做法应直接跳跃到重复字符的下一个位置left last_pos[ch] 1;错误3获取字符串长度方式错误错误写法int len sizeof(s);问题分析当s是函数参数指针时sizeof(s)获取的是指针本身的大小在64位系统上是8字节而不是字符串长度。正确做法使用int len strlen(s);需要包含#include string.h。错误4last_pos数组未初始化错误写法int last_pos[128];直接使用问题分析数组初始值为随机值内存中的垃圾数据会导致last_pos[ch]判断错误程序行为不可预测。正确做法必须将所有元素初始化为-1表示所有字符都未出现。可以用循环或memset(last_pos, -1, sizeof(last_pos));。四、完整解题模板int lengthOfLongestSubstring(char* s) { int len strlen(s); //计算字符串长度 if (len 0) return 0; int left 0; int max_len 0; int last_pos[128]; // 128个位置对应128个ASCII字符 // 初始化为-1 for (int i 0; i 128; i) { last_pos[i] -1; } //滑动窗口主程序 for (int right 0; right len; right) { char ch s[right]; //判断重复并移动左指针 if (last_pos[ch] left) { left last_pos[ch] 1; } //更新位置和最大长度 last_pos[ch] right; int cur_len right - left 1; if (cur_len max_len) { max_len cur_len; } } return max_len; }代码要点last_pos数组大小固定为128适用于所有ASCII字符。左指针left只向右移动从不回退保证了 O(n) 的时间复杂度。每次循环都更新max_len确保记录历史最大值。五、复杂度分析项目复杂度说明时间复杂度O(n)其中n是字符串长度。每个字符最多被右指针访问一次被左指针访问一次当它被移出窗口时。所有操作数组读写、比较均为 O(1)。空间复杂度O(1)last_pos数组大小固定为128与输入字符串长度无关。只使用了常数个额外变量left,max_len,right等。
郑州网站建设
网页设计
企业官网
