1.拿到题目后看到“无重复”字样就想到使用哈希表。已知ascii码只有128个所以可以创建一个长度为128的标记数组vis记录每种字符是否已被选中。使用for循环遍历整个字符串使用cnt记录当前子字符串的长度当遇到重复字符后进入下一次循环。如果遇到已经记录到字符串末尾的特殊情况则说明后面的循环不可能出现比本情况长度更长的字符串了可以直接跳出循环。2.初步写出的代码如下1. int lengthOfLongestSubstring(char* s) { 2. int maxCnt 0; 3. int vis[128]; 4. memset(vis, 0, sizeof(int) * 128); 5. 6. for (int i 0; i strlen(s); i){ 7. int cnt 0; 8. int cur i; 9. 10. while (cur strlen(s) vis[s[cur]] 0){ 11. vis[s[cur]] 1; 12. cnt; 13. cur; 14. } 15. maxCnt fmax(maxCnt, cnt); 16. 17. if (cur strlen(s)){ 18. break; 19. } 20. vis[s[i]] 0; 21. } 22. 23. return maxCnt; 24. }但代码没有通过可以总结出如下问题①代码实际上是滑动窗口双指针算法但是根据目前代码的逻辑每次进入下一次循环后只会将上一次的初始字符的标记置0而每次cur都会初始化为i因为vis[s[i 1]]的位置仍然是1这就导致下一层for循环根本进不去while循环②目前代码将strlen(s)放在了循环条件里而在C语言中strlen()的时间复杂度是O(n)这就意味着每次循环都会重新计算一遍字符串长度导致算法的时间复杂度退化为O(n2)。3.真正的滑动窗口思想应该是右指针cur是不回退的只管一直往前冲直到遇到重复而左指针i每次往前挪一步就吐出一个字符。修正后的完整代码如下1. int lengthOfLongestSubstring(char* s) { 2. int maxCnt 0; // 记录最长无重复子串的长度 3. int vis[128]; // 记录每个 ASCII 字符是否在当前窗口中0未出现1已出现 4. memset(vis, 0, sizeof(int) * 128); // 初始化 vis 数组为全0 5. int len strlen(s); // 字符串长度 6. 7. int cur 0; // 右指针窗口右边界 8. for (int i 0; i len; i){ // i 是左指针窗口左边界 9. // 向右扩展右指针直到遇到重复字符或字符串末尾 10. while (cur len vis[s[cur]] 0){ 11. vis[s[cur]] 1; // 标记当前字符为已出现 12. cur; // 右指针右移 13. } 14. // 计算当前窗口长度并更新最大值 15. maxCnt fmax(maxCnt, cur - i); 16. 17. // 如果右指针已经到末尾提前结束循环无需再移动左指针 18. if (cur len){ 19. break; 20. } 21. // 左指针右移前取消当前左边界字符的标记 22. vis[s[i]] 0; 23. } 24. 25. return maxCnt; 26. }该算法时间复杂度为O(n)空间复杂度为O(1)已是最优解法。4.修正后的代码定义了int len strlen(s)代替strlen(s)参与循环不再需要cnt可以直接用cur – i来代表子字符串长度右指针cur不再回头去重操作全都由操作左指针i改变左边界来实现。