前缀和+哈希表的存储(这里利用数组实现)

blablabla

样例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 100010;
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        /*
          N为10的五次方 Ai最长为10的五次方 所以最长会达到10的10次方 会爆int
          所以sum数组用long
        */
        long[] s = new long[N];
        int[] cnt = new int[N];

        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + scanner.nextLong();
        }

        /*
          暴力做法
          int res = 0;
          for (int r = 1; r <= n; r++) { // 右端点
            for (int l = 1; l <= r; l++) { // 左端点 
                int sum = s[r] - s[l - 1]; // 公式二
                if (sum % k == 0) res++;
            }
        }

        优化：
        当R固定时，在1 ~ R之间找到有多少个L满足(s[R] - s[L - 1]) % k == 0
        这其实就是我们第二层循环的含义，我们将循环条件简单的变一下：

        当R固定时，在0 ~ R - 1之间找到有多少个L满足(s[R] - s[L]) % k == 0
        可转换为：s[R] % k == s[L] % k

        即有多少个S[L]与S[R]的余数相同

        我们可以开一个新的数组，cnt[i]，表示余数是i的数有多少个

        关于cnt[0] =1的初始化: s[0] = 0, 而0%任何数都是0，所以cnt[0] = 1。

        */

        long res = 0;
        cnt[0] = 1;
        for (int i = 1; i <= n; i++) {
            res += cnt[(int)(s[i] % k)];
            cnt[(int)(s[i] % k)]++;
        }
        System.out.println(res);
    }
}