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)，表示数组的长度。

接下来一行包含 n 个整数，表示数组中的元素。

输出描述

输出一个整数，表示满足要求的最长区间的长度。

示例 1

输入

5
1
2
3
4
5

输出

2

示例 2

输入

5
1
2
3
4
6

输出

3

说明

在第二个样例中，最长的区间是 [2, 4]，其和为 2 + 3 + 4 = 9，可以被 7 整除。

思路

使用前缀和来维护子区间和，并使用哈希表记录模 7 余数第一次出现的位置。如果后面再次出现相同的模 7 余数，那么这两个位置之间的子数组之和模 7 余数为 0。

C++ 代码

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

int main() {
    int n;
    cin >> n;
    int a[n + 1];
    a[0] = 0; // 前缀和数组的第一个元素为 0
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1]; // 计算前缀和
    }
    unordered_map<int, int> mp; // 哈希表记录模 7 余数第一次出现的位置
    mp[0] = 0; // 将 0 的第一次出现位置设置为 0
    int maxLen = 0; // 记录最长区间的长度
    for (int i = 1; i <= n; i++) {
        int mod = a[i] % 7; // 计算当前前缀和模 7 的余数
        if (mp.count(mod)) { // 如果该余数在哈希表中存在
            maxLen = max(maxLen, i - mp[mod]); // 更新最长区间长度
        } else { // 如果该余数不在哈希表中
            mp[mod] = i; // 记录该余数第一次出现的位置
        }
    }
    cout << maxLen << endl;
    return 0;
}

代码解释

1. 使用 unordered_map 来存储每个模 7 余数第一次出现的位置。
2. 遍历数组，计算每个前缀和模 7 的余数。
3. 如果该余数已经存在于 unordered_map 中，则说明在该位置之前存在一个子区间，其和可以被 7 整除。更新最长区间长度。
4. 否则，将该余数及其第一次出现的位置记录到 unordered_map 中。
5. 最后输出最长区间长度。