蓝桥与力扣刷题（蓝桥k倍区间）

题目：给定一个长度为 N 的数列，A1,A2,⋯AN​，如果其中一段连续的子序列 Ai,Ai+1,⋯Aj( i≤j ) 之和是 K 的倍数，我们就称这个区间[i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入描述

第一行包含两个整数 N 和 K( 1≤N,K≤105 )。

以下 N 行每行包含一个整数 AiAi​ ( 1≤Ai≤105 )

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例 示例

输入

5 2 1 2 3 4 5

输出

6

解题思路+代码：(引用题解区 作者：风之理

解题思路

①前缀和：是每一个都是前面累加的（第一个是0+第一个） ②前缀和%K==》可以找到K=0，它一定是K的倍数 ③理解一个东西：任意两个前缀和的差值就是一个区间 ④而前缀和的差值为0，也一定是K的倍数 ⑤（3，3，3，3）---》任意两个组合：（n*(n-1)/2))

代码：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); long N= sc.nextInt(); long K= sc.nextInt(); long sum=0; long [] n1=new long[100010]; long [] n2=new long[(int) K]; for (int i = 0; i < N; i++) { long s= sc.nextInt(); n1[i+1]=n1[i]+s; n2[(int)(n1[i+1]%K)]++; } sum +=n2[0]; for (int i = 0; i < K; i++) { sum+=(n2[i]-1)*n2[i]/2; } System.out.println(sum); sc.close(); } }

 个人想了这题很久，但是提交代码只能通过两个用例：

总结： 个人认为这题还是有点难，ai之后发现高效的解法需要用到前缀和与哈希表来计算，大家也可参考大佬的解题思路~