让我们从一道面试手撕题出发，开始我们的字符串的探索之旅~！-一一网

前言

当当，笔者可没有标题党喔，这是笔者近期面试字节飞书前端开发岗时遇到的一道真实面试题，本着独乐乐不如众乐乐的观念，让我们以它为切入点，开始我们的字符串探索之旅吧。

关键词：手撕代码、字符串方法、字符串相关常考算法

题目概览

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

例1：
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
复制代码

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
复制代码

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
复制代码

?题目分析

首先我们需要清楚无重复字符的最长子串概念：包含在给定字符串中一个连续的不包含重复字符的子字符串，

其次我们需要留意返回的是长度还是具体子串，这里注意要求我们返回的只是子串的长度。

那可想而知遍历字符串的操作是必有的，以及关键是如何确定结果子串的起始与终点位置。

答案

PS：不想这么快揭晓谜题的友友可以先自己试试，这里提供笔者根据资料和自己理解整理的两种解法加代码注释。

解法1 滑动窗口（Tc O(n) Sc O(1)）

tip：滑动窗口的思想在线性结构的数据结构里常见，包括TCP控制可靠性的核心也是滑动窗口的思想，这里给自己留个作业，届时整理好了滑动窗口相关应用与算法会单开一篇再发布出来：）

截屏2022-03-18 下午5.17.29.png

var lengthOfLongestSubstring = function(s) {
    // 初始化空的str作为我们的滑动窗口
    let str = ''; 
    // 预设最长不重复子串长度为0  
    let length = 0;
    for (let i = 0; i < s.length; i++) {
       if (str.indexOf(s[i]) == -1) {
           // 如果当前窗口不包含s[i]，就在str串尾追加s[i]
           str += s[i]
       } else {
           // 如果当前窗口包含s[i]，就在滑动窗口长度和之前记录的length长度里取最值
           // ！这里注意先取大值之后再滑动
           length = Math.max(str.length,length);
           // 从str头部到第一个与s[i]值相等的位置都截掉，在str串尾追加s[i]，实现窗口滑动
           str = str.slice(str.indexOf(s[i]) + 1) + s[i];
       }
    }
    // 最后别忘记在滑动窗口长度和之前记录的length长度里取最值
    return  Math.max(length, str.length);
};
复制代码

解法2 暴力解法之三重循环（Tc O(n^3) Sc O(1)）

暴力解法是在没有其他更好的思路时的最后一个保底选项，可以看到暴力解法下的测试结果并不是很理想，但是解决问题（mianshi）时有思路远胜于没有，所以也可以看看暴力解法的思路垫个底。
截屏2022-03-18 下午4.19.51.png

var lengthOfLongestSubstring = function (s) {
    //若传入字符串长度为0则直接返回0不做处理；
    if (s.length < 1) {   
        return 0;
    }
    //初始化最长子串长度为1；
    let max = 1;   
    //每次子串起始位置下标右移，都让子串长度计数单位为1;只是因为每次起始位置变化，子串就变成了新的子串。
    for (let i = 0; i < s.length; i++) {
        let curLength = 1;   
        //j指针用于控制子串末位下标 
        for (let j = i + 1; j < s.length; j++) {   
             // diff用于标识当前子串是否每个字符都不相同
            let diff = 1;  
            //将子串末位字符与子串里所有字符比较
            for (let k = i; k < j; k++) {      
                if (s[j] === s[k]) {
                    diff = 0;
                }
            }
            if (diff) {
                //都不相同的话，当前子串长度计数变量加一
                curLength++; 
                //保存最长子串位数
                max = Math.max(max,curLength);
            } else {
                break;
            }
        }
    }
    return max;
};
复制代码