求解最长无重复字符子串长度的C++代码运行时错误排查

问题描述 #

给定字符串s，找出最长无重复字符子串的长度。编写的C++代码如下：

int lengthOfLongestSubstring(string s) {
        map<string,int> mp;
        vector<string > v;
        int ms=0;
        int l=s.length();
        if(l==1) return 1;
        for(int i=0;i<l;i++)
        {
            int cs=0;
            if(v[0]==v[s[i]])
            {
                cs=v.size();
                ms=max(cs,ms);
                v.clear();
                v.push_back({s[i]});
            }
            else
            {
                v.push_back({s[i]});
                cs=v.size();
                ms=max(cs,ms);
            }
        }
        return ms;
    }

运行错误信息 #

Line 518: Char 69: runtime error: applying non-zero offset 18446744073709551615 to null pointer (basic_string.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/basic_string.h:527:69

错误原因分析 #

• 空容器非法访问：代码初始化时vector<string> v是空的，循环中直接访问v[0]会触发越界访问，这是导致报错的直接原因。
• 重复判断逻辑完全错误：v[s[i]]是错误写法——s[i]是char类型，不能作为vector的索引；且代码仅对比容器第一个元素，未检查整个容器内是否存在当前字符，完全无法正确识别重复。
• 冗余无效代码：map<string,int> mp全程未使用，属于冗余定义。
• 边界场景处理缺失：空字符串、全重复字符（如"aaaaa"）等场景未覆盖，逻辑存在漏洞。

修正后的代码（滑动窗口最优解） #

int lengthOfLongestSubstring(string s) {
    unordered_set<char> charSet;
    int left = 0;
    int maxLen = 0;
    int n = s.size();
    
    for (int right = 0; right < n; ++right) {
        // 遇到重复字符时，移动左指针直到窗口内无重复
        while (charSet.find(s[right]) != charSet.end()) {
            charSet.erase(s[left]);
            ++left;
        }
        charSet.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

代码说明 #

• 采用滑动窗口法维护当前无重复字符的子串范围，时间复杂度O(n)，空间复杂度O(min(m,n))（m为字符集大小）。
• 用unordered_set快速判断当前字符是否在窗口内，平均查找、插入、删除时间复杂度均为O(1)。
• 右指针遍历每个字符，若遇到重复则左指针右移，直到窗口内消除重复；每次更新窗口后计算当前长度，维护最大长度值。

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