面试题：C++ STL 迭代器 begin 的反向迭代运用之性能优化与算法融合

Question

在一个包含大量整数（假设数量级为10万以上）的std::deque<int> 容器中，使用rbegin反向迭代器实现一个算法，找到连续三个元素之和最大的子序列，要求在实现过程中考虑性能优化，例如减少不必要的计算和内存访问。请详细描述你的算法思路，并给出核心代码实现，同时分析该算法的时间复杂度和空间复杂度。

Answer 1

算法思路

1. 使用反向迭代器 rbegin 从 std::deque<int> 的末尾开始遍历。
2. 维护一个窗口大小为3的滑动窗口，计算窗口内元素的和。
3. 每次移动窗口时，通过减去离开窗口的元素并加上进入窗口的元素来更新窗口和，避免重复计算整个窗口的和，以此优化性能。
4. 记录最大的窗口和及其对应的起始位置。

核心代码实现

#include <iostream>
#include <deque>

std::pair<int, std::deque<int>::const_reverse_iterator> findMaxSumSubsequence(const std::deque<int>& deq) {
    if (deq.size() < 3) {
        throw std::invalid_argument("deque must contain at least 3 elements");
    }

    auto rstart = deq.rbegin();
    auto rend = deq.rend();
    int maxSum = *rstart + *(rstart + 1) + *(rstart + 2);
    auto maxRStart = rstart;

    for (auto it = rstart + 3; it != rend; ++it) {
        int currentSum = maxSum - *(it - 3) + *it;
        if (currentSum > maxSum) {
            maxSum = currentSum;
            maxRStart = it - 2;
        }
    }

    return {maxSum, maxRStart};
}

时间复杂度分析

该算法只遍历一次 std::deque<int>，除了初始化窗口的和之外，每次窗口移动只进行常数次操作（一次减法和一次加法）。因此，时间复杂度为 $O(n)$，其中 $n$ 是 std::deque<int> 中元素的数量。

空间复杂度分析

该算法只使用了几个额外的变量（如 maxSum、maxRStart 等），这些变量占用的空间与输入规模无关。因此，空间复杂度为 $O(1)$。