【LeetCode】3. 无重复字符的最长子串

文章目录

• 题目链接
• 注意点
• 解法
• 遇到问题
• 小结

题目链接

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

注意点

解法

解法1：散列法

利用256的数组存储字符串中每个字符的出现位置，初始值未-1，表示没有出现过。

若是当前遍历字符没有出现过，则将出现位置更新；

若是当前遍历字符出现过，则说明出现了重复字符，，计算无重复字符串的长度，并更新无重复字符串的起点，最后将该字符出现位置更新。

这里注意，更新起点后，在旧起点和新起点之间的字符的出现位置要置为-1。

执行用时 :

12 ms

, 在所有 C++ 提交中击败了

81.27%

的用户

内存消耗 :

8.5 MB

, 在所有 C++ 提交中击败了

100.00%

的用户

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> hash(256,-1);
        int start=0,res=0;
        if(s.size()==0) return 0;
        for(int i=0;i<s.size();i++){
            if(hash[s[i]]!=-1){
                res=max(i-start,res);
                while(start<hash[s[i]]+1){
                    hash[s[start++]]=-1;
                }
            }
            hash[s[i]]=i;
        }
        res=max((int)s.size()-start,res);//因为写代码时是遇到重复的才计算res,所以可能出现整个字符串都没有重复字符的情况，故最后循环结束要再计算一次res
        return res;
    }
};
           

遇到问题

因为写代码时是遇到重复的才计算res,所以可能出现整个字符串都没有重复字符的情况，故最后循环结束要再计算一次res。

小结

利用hash数组存储字符出现的位置

动态维护无重复字符串的起点