如何将最长无重复字符子串求解优化至O(n)时间复杂度？

你的原解法是暴力枚举思路，双重循环带来的O(n²)时间复杂度在字符串较长时效率偏低。要优化到O(n)时间复杂度，我们可以用滑动窗口（双指针）+ 哈希表记录字符位置的方案，只需要一次遍历就能完成计算。

核心优化思路 #

1. 用left和right两个指针标记当前无重复子串的左右边界，初始均指向字符串开头。
2. 用哈希表存储每个字符最近一次出现的索引，快速判断当前字符是否在当前窗口内重复。
3. 遍历right指针逐个访问字符：
   • 如果当前字符已在哈希表中，且它的索引 >= left（说明重复字符在当前窗口内），就把left移动到该字符上次出现位置的下一位，确保窗口内无重复。
   • 更新当前字符的最新索引为right。
   • 计算当前窗口长度（right - left + 1），同步更新全局最大长度。

优化后的C++代码 #

#include<bits/stdc++.h>
using namespace std;

int lengthOfLongestSubstring(string s) {
    if (s.empty()) return 0;
    unordered_map<char, int> charIndexMap;
    int maxLen = 0;
    int left = 0;

    for (int right = 0; right < s.size(); ++right) {
        // 若当前字符在窗口内重复，移动左边界到重复位置的下一位
        if (charIndexMap.find(s[right]) != charIndexMap.end() && charIndexMap[s[right]] >= left) {
            left = charIndexMap[s[right]] + 1;
        }
        // 更新当前字符的最新出现位置
        charIndexMap[s[right]] = right;
        // 计算当前窗口长度，更新最大长度
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    string str1 = "abcabcbb";
    cout << "输入\"abcabcbb\"的结果：" << lengthOfLongestSubstring(str1) << endl; // 输出3

    string str2 = "bbbbb";
    cout << "输入\"bbbbb\"的结果：" << lengthOfLongestSubstring(str2) << endl; // 输出1

    string str3 = "abcsabcds";
    cout << "输入\"abcsabcds\"的结果：" << lengthOfLongestSubstring(str3) << endl; // 输出4
    return 0;
}

代码说明 #

• 哈希表charIndexMap把字符重复检查的时间开销降到O(1)，避免了原解法中每次重新遍历检查的冗余操作。
• 整个过程仅遍历一次字符串，每个字符最多被left和right各访问一次，最终时间复杂度为O(n)。
• 空间复杂度为O(min(m, n))，其中m是字符集的大小（比如ASCII字符集为128），n是字符串长度。

内容的提问来源于stack exchange，提问作者YOGENDRA SINGH