题目

image

暴力（枚举所有子串）

枚举所有可能的子串起点和终点，对每个子串检查是否有重复字符，记录最长的合法长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            unordered_set<char> seen;
            for (int j = i; j < n; j++) {
                if (seen.count(s[j])) break; // 出现重复，本次子串到此为止
                seen.insert(s[j]);
                ans = max(ans, j - i + 1);
            }
        }

        return ans;
    }
};

  • 时间复杂度：O(n²)（外层枚举起点，内层枚举终点）
  • 空间复杂度：O(min(n, m))，m 是字符集大小
  • 问题：每换一个起点 i，内层都要重新扫一遍。

优化（滑动窗口+哈希集合）

用双指针维护一个窗口 [left, right]，保证窗口内没有重复字符。右指针不断右移，一旦发现重复，就不断收缩左指针（把左边的字符移出集合），直到窗口内不再有重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int left = 0, ans = 0;

        for (int right = 0; right < s.size(); right++) {
            while (window.count(s[right])) {
                window.erase(s[left]);
                left++;
            }
            window.insert(s[right]);
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

  • 时间复杂度：O(n)（right 和 left 都是单向移动，最多各走 n 步，均摊下来是线性）
  • 空间复杂度：O(min(n, m))
  • 比暴力法快一个量级，但左指针有时要一步一步挪，不是最快的收缩方式。

最优（滑动窗口 + 哈希映射）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> lastIndex; // 字符 -> 最后出现的下标
        int left = 0, ans = 0;

        for (int right = 0; right < s.size(); right++) {
            char c = s[right];
            if (lastIndex.count(c) && lastIndex[c] >= left) {
                left = lastIndex[c] + 1; // 直接跳过重复字符，无需逐步移动
            }
            lastIndex[c] = right;
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

  • 时间复杂度：O(n)，只需一次遍历，且每一步都是 O(1) 操作，没有内层收缩循环
  • 空间复杂度：O(min(n, m))

由于题目提到字符集包括英文字母、数字、符号和空格（ASCII 范围内），也可以把 unordered_map 换成大小 128 或 256 的数组，进一步减少哈希开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int lastIndex[256];
        fill(begin(lastIndex), end(lastIndex), -1);
        int left = 0, ans = 0;

        for (int right = 0; right < s.size(); right++) {
            unsigned char c = s[right];
            if (lastIndex[c] >= left) {
                left = lastIndex[c] + 1;
            }
            lastIndex[c] = right;
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};