子序列匹配不要求元素连续，只需保持相对顺序，应使用贪心双指针法遍历主数组逐个匹配子序列元素，时间复杂度O(n)，标准库无现成函数，需手写；注意迭代器顺序、字符串类型安全及索引记录需求。
子序列匹配和子数组匹配不是一回事
很多人一看到“在数组中搜索子序列”，下意识用 std::search 或双指针扫连续段，结果逻辑错——子序列不要求连续，只要求元素相对顺序一致。比如在 {1,3,2,4,5} 中，{1,2,5} 是子序列，但不是子数组。
判断是否为子序列，核心是「贪心匹配」：遍历主数组，对子序列每个元素按顺序找第一个匹配项。
- 时间复杂度固定为
O(n)（n为主数组长度），不随子序列长度显著上升 - 不能用
std::find_first_of，它只管存在性，不管顺序 - 若需返回所有匹配起始位置或方案数，问题升级为动态规划，但日常判断存在性无需那么重
手写贪心匹配函数最直接可靠
标准库没有现成的「子序列判定」函数，std::search 匹配的是连续子数组，std::find_end 同理。必须自己写一个两指针逻辑。
示例代码（泛型，支持任意随机访问容器）：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
template <typename Iter1, typename Iter2>
bool is_subsequence(Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2) {
while (begin2 != end2 && begin1 != end1) {
if (*begin1 == *begin2) ++begin2;
++begin1;
}
return begin2 == end2;
}
// 用法：
std::vector<int> arr = {1,3,2,4,5};
std::vector<int> sub = {1,2,5};
bool found = is_subsequence(arr.begin(), arr.end(), sub.begin(), sub.end()); // true
- 注意两个迭代器各自推进：主数组始终前进，子序列仅在匹配时前进
- 如果子序列为空（
begin2 == end2），函数立即返回true，符合数学定义 - 别传反迭代器顺序，否则行为未定义
用 std::string 处理字符子序列要小心类型
如果操作的是 std::string，看起来可以复用上面模板，但容易踩坑：
-
std::string::c_str()返回const char*，不能直接喂给泛型函数——指针类型不满足迭代器要求（缺少operator++等） - 正确做法是用
.begin()/.end()，或显式构造std::string_view避免拷贝 - 如果子序列含空格或 null 字符，
c_str()截断，std::string本身无此问题
错误示范：is_subsequence(s.c_str(), s.c_str()+s.size(), t.c_str(), ...) —— 编译不过或运行崩溃。
需要定位子序列在原数组中的索引怎么办
上面函数只返回 bool，但有时你需要知道每个匹配元素在原数组里的下标（比如高亮显示或调试）。这时不能只用迭代器，得带索引走：
std::vector<size_t> find_subsequence_indices(
const std::vector<int>& arr,
const std::vector<int>& sub) {
std::vector<size_t> indices;
size_t i = 0, j = 0;
while (i < arr.size() && j < sub.size()) {
if (arr[i] == sub[j]) {
indices.push_back(i);
++j;
}
++i;
}
return (j == sub.size()) ? indices : std::vector<size_t>{};
}
- 返回空
vector表示不匹配；非空则包含子序列各元素在arr中的下标 - 这个版本不可泛型化为任意容器，因为依赖
.size()和operator[]，但对std::vector和原始数组足够用 - 如果原数组很大且子序列很短，提前终止比先建完整索引更省内存
