借助map辅助,用map记录每一个字符的最大的下标,用left记录没有重复字符子串的起始位置,空间复杂度和时间复杂度均为O(n)。
class Solution { public: /** * * @param s string字符串 * @return int整型 */ int lengthOfLongestSubstring(string s) { // write code here int size = s.size(); if (size < 1) return 0; unordered_map<char, int> um; int maxLen = 0, left = 0; // left记录上一个没有重复的位置 for (int i = 0; i < size; ++i) { if (um.find(s[i]) != um.end()) { // 如果在map里 left = max(left, um[s[i]] + 1); } maxLen = max(maxLen, i - left + 1); um[s[i]] = i; } return maxLen; } };