算法分析

朴素做法 $(n^2)$

for(int R = 1;i <= n;R ++) //右端点
        for(int L = 1;L <= R;L++)//左端点
        {
            int sum = s[R] - s[L - 1];
            if(sum % k == 0) res ++;
        }

• 1、当R固定时，在1 ~ R之间找到有多少个L，满足(s[R] - s[L - 1]) % k == 0
  即 当R固定时，在1 ~ R - 1之间找到有多少个L，满足(s[R] - s[L]) % k == 0

• 2、使用空间换时间的优化，通过一个cnt[]数组，来记录余数是i的数有多少个

可优化到$O(n)$

for(int R = 1;R <= n;R ++)
    {
        res += cnt[s[R] % k];
        cnt[s[R] % k] ++;
    }

时间复杂度 $O(n)$

Java 代码

import java.util.Scanner;

public class Main {
    static int[] s = new int[100010];//记录前缀和
    static int[] cnt = new int[100010];//记录余数是i的数有多少个
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        for(int i = 1;i <= n;i++)
        {
            s[i] = (s[i - 1] + scan.nextInt()) % k;
        }
        long res = 0;
        cnt[0] = 1;//余数为0时，已经占一个
        for(int i = 1;i <= n;i++)
        {
            res += cnt[s[i]];
            cnt[s[i]] ++ ;
        }
        System.out.println(res);
    }
}