LeetCode第3题：求无重复字符的最长子串——高效解法分析

针对「找出无重复字符的最长子串」这个经典问题，你提供的这段代码是个性能拉满的优化版滑动窗口实现，咱们来一步步拆解分析：

实现代码 #

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int dic[256];
        memset(dic, -1, sizeof(dic));
        int len = s.size();
        int idx = -1;
        for (int i = 0;i < len;i++) {
            char c = s[i];
            if (dic[c] > idx)
                idx = dic[c];
            ans = max(ans, i - idx);
            dic[c] = i;
        }
        return ans;
    }
};

核心思路：跳过式滑动窗口 #

这是对传统滑动窗口的优化，用数组替代哈希表（因为ASCII字符范围固定）来记录字符的最新出现位置，直接跳过重复字符的区间，避免左指针逐步移动的冗余操作：

• 初始化dic[256]为-1，用来存储每个ASCII字符最后一次出现的索引值
• idx代表当前无重复子串的左边界，当遍历到字符s[i]时，如果它之前出现过，且上次出现的位置在当前窗口内（dic[c] > idx），就把左边界直接更新为dic[c]，相当于跳过了重复字符之前的所有元素
• 每次循环计算当前窗口的长度i - idx，和ans比较后保留最大值，同时更新当前字符的最新出现位置为i

时间复杂度推导 #

这个算法的时间复杂度是O(n)，其中n是输入字符串的长度：

• 我们只对字符串进行了一次线性遍历，每个字符仅被访问一次
• 数组的查询、赋值操作都是O(1)的常数时间操作
• 没有嵌套循环或者额外的线性扫描步骤，整体执行时间和字符串长度成正比

空间复杂度 #

空间复杂度为O(1)：

• 这里用了一个固定大小的数组dic[256]，不管输入字符串的长度是多少，数组的大小始终是256（覆盖所有ASCII字符），属于常数级别的空间开销

内容的提问来源于stack exchange，提问作者heiheihei hahaha