题解 | #最长不含重复字符的子字符串#

第四十八题

第一种 二重循环  并用hash判断是否重复  不是题目像要的算法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        if(s.size()<=1)
            return 1;
        // write code here
        // 遍历两次二维数组
        int len=0;
        int temp=1;
        map<char,int> start;
        for(int i=0;i<s.length();i++)
        {
            start.clear();
            start[s[i]] =1;
            temp=1;
            for(int j=i+1;j<s.length();j++)
            {
                if(start [s[j]]!= 1)
                {
                    start[s[j]]=1;
                    temp++;
                }
                else
                    break;
            }
            len=max(len,temp);
        }
        return len;
    }
};

第二种 利用hash一次遍历

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        if(s.size()<=1)
            return 1;
        // write code here
        // 不需要二重循环 只需要在hash遇到的时候 修改开始的指针p就好
        
        map<char,int>hash;
        // p用来计算没有重复字符串的子串的起始位置
        int p=-1;
        int len=0;
        for(int i=0;i<s.length();i++)
        {
            // 如果说 出现过这个数字 并且这个数字在这段字符串中间（出现的位置大于p，则p要更新）
            if(hash.count(s[i])!=0 &&  hash[s[i]] > p )
                p=hash[s[i]];
            // 记录下当前的值，更新长度
            hash[s[i]]=i;
            len=max(len,i-p);
        }
        return len;
    }
};

第三种 对第二种map的优化

map 的复杂度 比直接访问数组大一些，所以创建一个数组用来记录是否有数值即可

使用方法同上

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        if(s.size()<=1)
            return 1;
        // write code here
        // map的复杂度 比直接访问数组大一些，所以创建一个数组用来记录是否有数值即可
        // 后面算法一样 都是让p表示子串的起始位置
        vector<int>hash(128,-1);
        int p=-1;
        int len=0;
        for(int i=0;i<s.length();i++)
        {
            if(hash[s[i]] > p )
            {
                len=max(len,i-p-1);
                p=hash[s[i]];
            }
            hash[s[i]]=i;
        }
        // 不用每次都更新 只要在有变化 和最后一次的时候更新就好
        len=max(len,int(s.length()-1-p));
        return len;
    }
};