LeetCode无重复字符的最长子串暴力法C++代码运行错误求排查

代码存在的核心问题 #

• vector<char> substr 声明位置错误：你把它定义在了内层for(j)循环的内部，每次j递增都会重新创建一个空的substr，之前存储的无重复字符会全部丢失，永远只能存当前j对应的单个字符。
• 判断逻辑写反：std::find(substr.begin(),substr.end(),s[j]) != substr.end() 这个表达式的含义是当前字符已经在substr中存在，你现在的代码是存在才往里面加、计数，不存在反而break，和你要的逻辑完全相反。
• 逻辑效率可优化：用vector+std::find判断存在的时间复杂度是O(k)（k是当前子串长度），可以用unordered_set<char>或者ASCII数组代替，判断存在的时间复杂度降到O(1)。

修正后的代码（保留你的暴力遍历思路） #

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_length = 0;
        int n = s.length();
        for(int i=0;i<n;i++){
            int temp = 0;
            vector<char> substr; // 移到内层j循环外，每个i对应一个新的子串存储容器
            for(int j=i;j<n;j++){
                if(substr.empty()){
                    substr.push_back(s[j]);
                    temp++;
                }
                // 条件修正：没找到重复才新增字符，找到重复就跳出循环
                else if( std::find(substr.begin(),substr.end(),s[j]) == substr.end()){
                    substr.push_back(s[j]);
                    temp++;
                }else{
                    break;
                }
            }
            max_length = max(temp,max_length);
        }
        return max_length;
    }
};

更高效的实现方案（滑动窗口+哈希集合，时间复杂度O(n)） #

暴力法的时间复杂度是O(n²)，对于长字符串效率较低，可以用滑动窗口思路优化：

#include <unordered_set>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                occ.erase(s[i - 1]);
            }
            while (rk < n && !occ.count(s[rk])) {
                occ.insert(s[rk]);
                ++rk;
            }
            ans = max(ans, rk - i);
        }
        return ans;
    }
};

内容的提问来源于stack exchange，提问作者260-sai suraj K