蓝桥杯‘子串简写’题别再用暴力了！手把手教你二分优化，效率提升百倍

蓝桥杯‘子串简写’题：从暴力枚举到二分优化的思维跃迁

第一次参加蓝桥杯时，我盯着那道"子串简写"的题目整整半小时毫无头绪。直到比赛结束前才勉强写出暴力解法，结果自然是超时。后来复盘时才恍然大悟：原来只需要一个简单的二分查找，就能让效率提升百倍。本文将带你完整重现这个思维升级的过程。

1. 问题本质与暴力解法剖析

题目要求统计字符串中所有满足特定条件的子串数量：子串首字符为c1，尾字符为c2，且长度≥k。表面看这似乎需要检查所有可能的子串组合，但深入分析会发现隐藏的优化空间。

暴力解法的核心代码如下：

for(int i = 0; i < s.size(); i++) { if(s[i] != c1) continue; for(int j = i + 1; j < s.size(); j++) { if(j - i + 1 >= k && s[j] == c2) ans++; } }

这种双重循环的时间复杂度是O(n²)，当n达到10⁵时必然超时。但仔细观察会发现内层循环其实在做重复工作——每次遇到c1时，都在重新扫描整个后续字符串寻找c2。

暴力解法的三大痛点：

1. 重复扫描：对每个c1都重新检查后续所有字符
2. 无效计算：即使知道后续c2的位置，仍逐个检查
3. 缺乏预处理：没有利用字符串的静态特性

2. 优化思路的突破口

关键在于发现两个重要特征：

1. c2的位置是固定的，与当前c1无关
2. 对每个c2，我们只需要知道前面有多少个c1满足位置差≥k-1

这提示我们可以：

• 预处理记录所有c1的位置
• 对每个c2，在c1位置数组中快速统计满足条件的数量

优化思路演进表：

3. 二分查找的精妙应用

预处理阶段我们用一个数组pc1按顺序存储所有c1的位置。对于每个c2的位置j，我们需要统计pc1中有多少元素≤j-k+1。

vector<int> pc1; // 存储c1的位置 for(int i = 0; i < s.size(); i++) { if(s[i] == c1) pc1.push_back(i); if(s[i] == c2) { if(i - k + 1 < 0 || pc1.empty()) continue; int target = i - k + 1; // 二分查找pc1中≤target的最大索引 int l = 0, r = pc1.size() - 1; while(l < r) { int mid = (l + r + 1) >> 1; if(pc1[mid] <= target) l = mid; else r = mid - 1; } if(pc1[l] <= target) ans += (l + 1); } }

这段代码有几个关键点：

1. pc1数组天然有序，满足二分查找前提
2. 使用mid = (l + r + 1) >> 1确保不会死循环
3. 最终检查pc1[l] <= target避免边界错误

4. 复杂度分析与性能对比

假设字符串中c1出现m次，c2出现n次：

实际测试中，当n=10⁵时：

• 暴力解法无法在合理时间内完成
• 二分优化版本仅需约15ms

5. 调试技巧与常见陷阱

实现二分查找时容易遇到以下问题：

边界条件处理：

• 空pc1数组情况
• 所有c1位置都大于target
• 所有c1位置都小于target

二分查找变体选择：

• 这里需要找最后一个≤target的元素
• 使用mid = (l + r + 1) >> 1而非mid = (l + r) >> 1
• 循环条件while(l < r)而非while(l <= r)

调试小技巧：

1. 先写暴力解法作为正确性验证
2. 对小样例打印pc1数组和二分过程
3. 测试极端情况：k=1，全c1，全c2等

6. 思维拓展与其他应用场景

这种"预处理+二分统计"的模式适用于许多字符串问题：

1. 区间统计问题：统计满足某种区间条件的元素对
2. 最近邻查找：快速找到距离某个位置最近的特定字符
3. 频率统计：统计特定字符在某个区间内的出现次数

例如LeetCode 792题"匹配子序列"，就可以用类似的思路将时间复杂度从O(n²)优化到O(n log m)。