基于STL或Ranges算法高效查找满足谓词的n个连续元素

你提到的这个查找连续n个47的函数，确实可以做得更高效且简洁——既不用提前分配内存存所有谓词结果，也不用在最坏情况下做O(n*m)的重复检查。咱们一步步来拆解优化思路：

现有方案的核心问题 #

你的原始实现有两个明显的痛点：

• 不必要的内存分配：不管目标序列在前半段还是后半段，都要先把整个vector的每个元素转换成bool存起来，浪费内存和预处理时间。
• 提前全量计算：哪怕前几个元素就找到了目标连续序列，也还是会遍历完整个vector生成predicate_result，做了无用功。

而你担心的手动迭代+std::all_of的方案，确实在最坏情况（比如整个序列只有最后n个是47）下会有O(n*m)的时间复杂度，效率太低，确实不推荐。

更高效简洁的实现方案 #

我们可以用滑动窗口+状态追踪的方式，只遍历一次原序列，同时记录当前连续47的数量，一旦达到n就立刻返回起始迭代器，完全不需要额外内存分配：

#include <vector>
#include <iterator>

auto find_n_47s(const int n, const std::vector<int>& values) {
    if (n <= 0 || values.size() < static_cast<size_t>(n)) {
        return values.end();
    }

    int current_streak = 0;
    auto start_it = values.begin();

    for (auto it = values.begin(); it != values.end(); ++it) {
        if (*it == 47) {
            if (current_streak == 0) {
                start_it = it; // 记录当前连续47的起始位置
            }
            ++current_streak;
            if (current_streak == n) {
                return start_it; // 找到目标，直接返回
            }
        } else {
            current_streak = 0; // 中断连续，重置计数
        }
    }

    return values.end(); // 遍历完没找到
}

为什么这个方案更好？ #

• 时间复杂度最优：只需要遍历一次序列，时间复杂度是O(m)（m是vector的元素个数），最坏情况才会遍历完整个序列，一旦找到目标就提前返回。
• 无额外内存开销：不需要分配任何临时容器，只用到几个整型变量和迭代器，内存复杂度O(1)。
• 逻辑清晰简洁：没有复杂的STL算法嵌套，读起来一目了然，也容易维护。

补充边界情况处理 #

上面的实现已经考虑了几种关键边界情况：

• 当n≤0时，直接返回end()（不符合有效查找逻辑）
• 当vector的元素个数小于n时，不可能找到目标序列，直接返回end()
• 序列开头就有连续n个47的场景
• 序列中间或末尾出现连续n个47的场景

如果你偏好更“STL风格”的实现，也可以基于std::adjacent_find或自定义谓词，但上面的手动遍历方案在性能和简洁性上已经是最优选择了。

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