题目要求

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

• 提示：

• 0 <= s.length <= 5⁴
• s 由英文字母、数字、符号和空格组成

原题链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

解题

滑动窗口

1. 最开始的时候

1. 创建START、END指向字符串最前端的位置
2. 创建LENTH记录当前长度
3. 创建RESULT记录无重复字符的最长字串长度

1. 使用循环，向后移动END

1. 检查END指向的新字符是否与字串内的字符重复

• 如果重复，移动START到重复字符的下一个位置
• 如果不重复，则不移动

1. 重新计算LENTH=END-START+1
2. 对比当前LENTG和已记录的RESULT，取较大值为新RESULT

1. 上图中，左侧三步中均无重复字符

1. START停留在原地不动，END++

1. 右侧第一幅图中，END指向的新字符A与子串中字符A重复

1. START移动到原子串中字符A的下一个位置，即字符B所在位置
2. LENTH=3；
3. RESULT=3；

1. 右侧第二幅图中，END指向的新字符C与子串中字符C重复

1. START移动到原子串中字符C的下一个位置，即字符A所在位置
2. LENTH=2
3. RESULT=3

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        for (int index = 0; index < s.size(); index++)
        {
            end = index;
            for (int i = start; i < end; i++)
            {
                if (s[i] == s[end])
                {
                    start = i + 1;
                    //及时跳出
                    break;
                }
            }
            result = max(result, end - start + 1);
        }
        return result;
    }
};

哈希表

思路与滑动窗口相同，不同的是查找重复元素的方式

• 滑动窗口是用遍历字符串的方式
• 哈希表是用容器自带的find方法

需要注意的是：

1. 查找到重复元素后，要将表中记录的该元素的位置修改为最新位置
2. 由于重新确定区间后，不清楚到底少了哪些元素，所以判断重复元素时，应确保该位置在START之后

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        unordered_map<char, int>mp;
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (mp.find(s[i]) != mp.end() && mp[s[i]] >= start)
            {
                start = mp[s[i]] + 1;
            }
            mp[s[i]] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

桶优化

判断是否出现过时，利用vector容器代替哈希表以优化时间

• int[26]用于字母'a'-'z'或'A'-'Z'
• int[128]用于ASCII码
• int[256]用于扩展ASCII码

思路与前两种方法相同，不同的仍是检验重复的方法

1. 每次移动END，都将END指向的字符转化为ASCII码对应的数字
2. vector容器中对应的数字下标的值存储的是改数字最后出现的位置

1. 如vec[2]=3，意思是ASCII码中值为2的字符，目前最后一次出现在字符串中的第4个字符的位置

1. 判断END所指的字符在vector容器中存储的位置，是否大于START

• 如果大于，则修改START，指向存储的位置的下一个位置
• 否则，不操作START

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start(0), end(0), result(0);
        vector<int>v(128, -1);
        for (int i = 0; i < s.size(); i++)
        {
            end = i;
            if (v[int(s[i])] >= start)
            {
                start = v[int(s[i])] + 1;
            }
            v[int(s[i])] = end;
            result = max(result, end - start + 1);
        }
        return result;
    }
};

总结

力扣给这道题的分类是中等，对新手来说很难，而且还用到了两个指针，虽然上面的代码中用的是下标访问的方式，不是严格的指针，但也不容易，建议就是多看看题解，多写几遍代码，对于容器和重载的一些方法，可以随时去cplusplus网站查阅，边刷题边巩固