题目

题解

这道题是用滑动窗口法，用一个哈希表（或者vector或者unordered_set）存已经遍历过的字符和最近出现该字符的位置
若重复遇到该字符，更新哈希表，并更新最长子串的长度

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$

1. unordered_map法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //定义哈希表存每个字符的下标及对应的最近出现该字符的位置
        //这里的key值直接用的int，相当于用字符的ascll码来作为key
        //也可以用char
        unordered_map<int,int>m;
        int res=0, left=-1;//res存子串的最长长度，left存滑动窗口的开始的前一个位置
        for(int i=0; i<s.size(); ++i){//遍历字符串
            if(m.count(s[i])) left = max(left,m[s[i]]);//若该字符出现过，更新left指针的位置
            m[s[i]] = i;//更新哈希表
            res = max(res,i-left);//更新此时的最大长度
        }
        return res;
    }
};

2. vector法

这个方法在leetcode上测试更快一点
这个方法使用vector来代替哈希表，因为ascll表最多只有256个字符，而前128个字符就已经包括了所有我们常用的字母，数字，标点符号等。这里直接定义一个大小为128的数组来存每个字符最近出现的位置，该数组全部初始化为-1。res和left还是表示结果和滑动窗口的左边的前一个数。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int>m(128,-1);//区别！定义数组
        int res=0, left=-1;
        for(int i=0;i<s.size();++i){
            //区别！不用进行判断，直接更新left。
            //若不是重复数字，则m[s[i]]是-1，left必定大于等于-1，left不会更新
            left = max(left,m[s[i]]);
            m[s[i]] = i;//更新数组
            res = max(res,i-left);
        }
        return res;
    }
};