LeetCode第3题无重复字符最长子串代码编译错误求助

问题描述 #

给定一个字符串，找出其中不含重复字符的最长子串的长度，要求采用**滑动窗口（sliding window）**方法解决。

示例 #

• 示例1：

Input: s = "abcabcbb"
Output: 3
Explanation: 答案为"abc"，长度为3。

• 示例2：

Input: s = "bbbbb"
Output: 1
Explanation: 答案为"b"，长度为1。

• 示例3：

Input: s = "pwwkew"
Output: 3
Explanation: 答案为"wke"，长度为3。注意答案必须是子串，"pwke"是子序列而非子串。

错误代码及问题分析 #

以下是尝试实现的代码，但代码中的while循环存在逻辑错误，导致编译运行异常：

class Solution {
public:
    int lengthOfLongestSubstring(std::string s){
        
        int count{0};
        std::map<char,int> char_map;
        std::vector<char> char_vec;
        auto left{char_vec.begin()};
        auto right{char_vec.begin()};
        
        for(int i = 0; i < s.length(); i++){
            char_vec.push_back(s[i]);
            if(char_map.find(s[i]) != char_map.end()){
                char_map[s[i]]++;                    
            }
            else{
                char_map.insert(std::pair<char,int>{s[i],1});   
                
            }
            while(++right != char_vec.end() && char_map[*(right)] > 1){
                char_map[*(left++)]--;            
            }
            count = (count < std::distance(left,right)) ? std::distance(left,right) : count;   
        }
        return count;                
    }
};

核心问题点 #

1. 迭代器使用错误：
   • 每次向char_vec添加元素后，right指针被直接++，导致首次循环时right就指向char_vec.end()，循环条件永远不成立，无法正确收缩左边界。
   • 维护char_vec完全多余，原字符串s可以直接通过索引访问字符，无需额外存储，且vector迭代器在扩容时可能失效，增加复杂度。
2. 滑动窗口逻辑错误：
   • 当发现重复字符时，仅对char_map的计数减1，没有将左指针left移动到重复字符的下一个有效位置，无法保证窗口内始终无重复字符。
3. 效率问题：使用std::map不如std::unordered_map高效，甚至可以用数组（因为字符的ASCII范围有限）来存储字符出现的位置，进一步提升性能。

修正后的代码 #

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        int max_len = 0;
        // 用数组存储字符最后出现的索引，ASCII字符范围0-127
        int last_pos[128] = {0};
        // 滑动窗口左边界
        int left = 0;

        for (int right = 0; right < s.size(); ++right) {
            // 如果当前字符已在窗口内出现过，更新左边界到重复位置的下一位
            if (last_pos[s[right]] > left) {
                left = last_pos[s[right]];
            }
            // 更新当前字符的最后出现位置
            last_pos[s[right]] = right + 1;
            // 计算当前窗口长度并更新最大值
            int current_len = right - left + 1;
            if (current_len > max_len) {
                max_len = current_len;
            }
        }
        return max_len;
    }
};

修正说明 #

1. 用索引替代迭代器：直接使用整数left和right作为滑动窗口的边界，操作简单且避免迭代器失效问题。
2. 优化字符存储：利用ASCII字符范围固定的特点，用大小为128的数组存储每个字符最后出现的索引，比哈希表更快。
3. 正确收缩左边界：当遇到重复字符时，将左边界移动到该字符上一次出现位置的下一位，确保窗口内无重复字符。
4. 简化逻辑：去掉多余的char_vec，直接操作原字符串，减少内存占用和复杂度。

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