C++ 前缀和算法实现最长可被 7 整除的区间

给你 n 个数，分别是 a[1], a[2], ..., a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x], a[x+1], a[x+2], ..., a[y-1], a[y])的和能被 7 整除。输出区间长度。若没有符合要求的区间，输出 0。

输入描述

第一行一个整数 n (1 <= n <= 50000)，接下来是每一个整数

输出描述

一个最长的区间内容：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    vector<int> pre(n+1, 0); // pre[i]表示前i个数的前缀和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
        pre[i] %= 7; // 取模，避免整型溢出
    }
    int ans = 0;
    vector<int> last(7, -1); // last[i]表示前缀和为i的最后一个位置
    for (int i = 0; i <= n; i++) { // 枚举右端点y
        if (last[pre[i]] != -1) {
            int len = i - last[pre[i]];
            ans = max(ans, len);
        } else {
            last[pre[i]] = i;
        }
    }
    cout << ans << endl;
    return 0;
}

代码解释

使用前缀和数组 pre，pre[i] 表示前 i 个数的和。
对每个前缀和 pre[i] 取模 7，这样可以将前缀和的值限制在 0 到 6 之间，方便查找。
使用 last 数组记录每个前缀和值最后一次出现的位置。
枚举右端点 y，对于每个右端点，如果 last[pre[i]] 不等于 -1，说明存在一个区间 [last[pre[i]], i] 的和能被 7 整除，更新答案。
最后输出 ans，即最长区间的长度。

优化技巧

使用 map 来存储前缀和的值和位置，可以更方便地查找前缀和值最后一次出现的位置。
可以使用二分查找来加速 last 数组的查找。

应用场景

前缀和算法可以用于解决很多类似的问题，例如：

查找一个数组中所有子数组的和。
查找一个数组中所有和等于 k 的子数组。
查找一个数组中所有和为偶数的子数组。

希望本文能够帮助你理解和应用前缀和算法。