求解包含0、1、2的最小子串问题时遭遇TLE，求优化方案

核心优化点 #

• 替换unordered_map为固定大小数组：由于只需要统计'0'、'1'、'2'三个字符，用长度为3的数组（索引0、1、2分别对应三个字符的计数）替代哈希表，数组的访问、修改操作开销远低于哈希表，这是解决超时的关键。
• 提前边界判断：若字符串长度小于3，直接返回-1，避免后续无效计算。
• 收缩窗口逻辑优化：在找到包含所有字符的窗口后，持续收缩左边界并同步更新计数，确保不会错过更小的有效窗口。

优化后的代码 #

int smallestSubstring(string S) {
    int n = S.size();
    if(n < 3) return -1;
    
    int count[3] = {0}; // 分别统计'0','1','2'的出现次数
    int l = 0, cnt = 0;
    int minLen = INT_MAX;
    
    for(int r = 0; r < n; r++){
        int idx = S[r] - '0';
        if(count[idx] == 0){
            cnt++;
        }
        count[idx]++;
        
        // 当窗口包含全部三个字符时，尝试收缩左边界以找到更小窗口
        while(cnt == 3){
            minLen = min(minLen, r - l + 1);
            // 移动左指针并更新计数
            int leftIdx = S[l] - '0';
            count[leftIdx]--;
            if(count[leftIdx] == 0){
                cnt--;
            }
            l++;
        }
    }
    
    return minLen == INT_MAX ? -1 : minLen;
}

优化说明 #

• 数组替代哈希表：unordered_map的哈希冲突、内存开销会拖慢频繁的读写操作，而固定数组通过字符转索引直接访问，操作速度大幅提升，彻底解决超时问题。
• 循环逻辑简化：用for循环遍历右指针，代码结构更简洁，逻辑更直观。
• 提前过滤无效输入：直接处理长度不足3的字符串，减少不必要的循环执行。

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