题目

图片说明

思路

其实我也不会,单纯解读一下别人的代码
题目要求幸运子数组中所有数的和能被k整除
小学二年级数学知识我们知道:

图片说明

所以我们只需要计算数组和的前缀和,然后把前缀和求余k,再看看何时出现了一样的余数或者被k整除即可

为了判断何时出现了一样的余数,我们声明一个数组pos来记录这个余数第一次出现的位置,-1表示未出现过,并且让pos[0]=0(被k整除的情况)
这样每次把数组和求余k以后判断pos是否为-1,如果是-1就记录余数第一次出现的位置,如果不是-1,则直接拿当前数的位置减去pos的位置,看看长度是否为最大即可

代码

#include <iostream>
#include <memory.h>

using namespace std;

int main() {
    //工具人变量temp
    int temp;
    //数据的组数T
    int T;
    //幸运数字k
    int k;
    //数组长度n
    int n;
    //数组中前i个数的和除以k的余数
    int sum[100005] = {0};
    //以sum[i]%k为下标,记录这个余数出现的第一个位置,-1表示未出现过
    int pos[100005] = {-1};

    cin >> T;
    while (T-- > 0) {
        //清一下pos数组
        memset(pos, -1, sizeof(pos));
        //如果余数为0说明第1到第i个数字的和正好被k整除
        //即幸运子数组的长度为i
        pos[0] = 0;
        //最长幸运子数组的长度
        int maxLength = -1;
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> temp;
            sum[i] = sum[i - 1] + temp;
            sum[i] %= k;
            //看看这个余数之前有没有出现过
            //如果没出现过,记录出现的位置
            //如果出现过,记录一下数组长度
            if (pos[sum[i]] == -1) {
                pos[sum[i]] = i;
            } else {
                maxLength = max(maxLength, (int) (i - pos[sum[i]]));
            }
        }
        cout << maxLength << endl;
    }
}