3 无重复最长子串【c++,哈希表】

在这里插入图片描述

解题思路

滑动窗口+哈希表
unordered_map<char, int>temp_s记录单个字符和下标,记录每一次开始的下标left;
如果第i个字符不在哈希表中,就把这一个字符加进去,如果第i个字符在哈希表中,则left从i+1开始,子串长度为i-left+1
注:
找到的某一个字符不仅要在哈希表中,而且要在left和i之间才算,所以这里限制
if (it != temp_s.end()&&it->second>=left)

代码

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

THE END
分享
二维码
< <上一篇
下一篇>>