C++如何在数组中搜索一个子序列-C++-PHP中文网

子序列匹配不要求元素连续，只需保持相对顺序，应使用贪心双指针法遍历主数组逐个匹配子序列元素，时间复杂度o(n)，标准库无现成函数，需手写；注意迭代器顺序、字符串类型安全及索引记录需求。

c++如何在数组中搜索一个子序列

子序列匹配和子数组匹配不是一回事

很多人一看到“在数组中搜索子序列”，下意识用 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、代码审查。

下载

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
</int></int></typename>

注意两个迭代器各自推进：主数组始终前进，子序列仅在匹配时前进
如果子序列为空（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> indices;
    size_t i = 0, j = 0;
    while (i {};
}
</int></int></size_t>