当前位置：首页 > news >正文

蓝桥杯真题——k倍区间

news 2024/11/14 11:41:50

题目链接：2.k倍区间 - 蓝桥云课

题目描述

输入描述

输出描述

输入输出样例

示例

运行限制

解法一：暴力（一点分是一点分）

思路：

具体流程：

优缺点：

Java写法：

C++写法：

AC情况

时间复杂度和空间复杂度

解法二：前缀和+哈希表优化

优化思路：

算法实现：

代码解释：

Java写法：

C++写法：

这行代码：modCount.put(0L, 1L);

1. 前缀和的含义：

2. 初始化模值为 0：

3. 实际含义：

4. 避免漏掉边界情况：

运行时间

时间复杂度和空间复杂度

总结

1. 题目描述

2. 暴力解法

3. 优化思路：前缀和 + 哈希表

前缀和的思想：

使用哈希表：

关键点：

题目链接：2.k倍区间 - 蓝桥云课

注：下述题目描述和示例均来自蓝桥云客

题目描述

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

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

输入描述

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

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

输出描述

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

输入输出样例

示例

输入

输出

运行限制

最大运行时间：2s
最大运行内存: 256M

解法一：暴力（一点分是一点分）

思路：

暴力解法：通过两层嵌套循环，遍历所有可能的子数组区间 A[i] 到 A[j]，逐个计算每个子数组的和，然后判断是否为 K 的倍数。
外层循环用于选择子数组的起点 i，内层循环用于遍历从 i 开始的所有子数组并计算其和 total，判断 total % K == 0 是否成立。

具体流程：

输入处理：首先从输入中读取数列的长度 N 和倍数 K，然后将数列的元素存储在数组 nums 中。
两层循环：
- 外层循环遍历每一个起点 i。
- 内层循环从 i 开始，向后遍历，累加当前区间的和 total。
- 每次计算和 total 后，判断其是否为 K 的倍数，如果是，则增加结果 res。
输出结果：输出符合条件的子数组的数量 res。

优缺点：

时间复杂度：暴力解法的时间复杂度为 O(N^2)，因为外层循环遍历 N 次，每次内层循环最多遍历 N 次，导致总时间复杂度为 O(N^2)。当 N 最大为 10^5 时，这种复杂度不可接受，可能导致超时。不巧，这里的N最大还真是10^5
空间复杂度：空间复杂度为 O(N)，因为只使用了一个大小为 N 的数组来存储输入数据。

Java写法：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = sc.nextLong();long k = sc.nextLong();long[] nums = new long[(int)n];for(int i = 0; i < n; i++){// 将所有的整数都存储到数组之中nums[i] = sc.nextLong();}long res = 0;for(int i = 0; i < n; i++){long total = 0;for(int j = i; j >= 0; j--){if((total += nums[j]) % k == 0){// System.out.println(nums[i] + ":" + total);res++;}}}System.out.print(res);sc.close();}
}

C++写法：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;int main() {// 输入 N 和 Klong long n, k;cin >> n >> k;// 存储输入的数列vector<long long> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];  // 输入每个数字}long long res = 0;  // 结果计数器// 遍历所有的子数组区间for (int i = 0; i < n; i++) {long long total = 0;  // 当前子数组的和for (int j = i; j >= 0; j--) {total += nums[j];  // 计算从 i 到 j 的子数组和if (total % k == 0) {  // 如果当前和是 K 的倍数res++;  // 增加结果计数器}}}cout << res << endl;  // 输出结果return 0;
}

AC情况

时间复杂度和空间复杂度

时间复杂度：O()，遍历一次数组，每次操作都在常数时间内完成。
空间复杂度：O(K)，哈希表最多存储 K 个不同的模值。

解法二：前缀和+哈希表优化

要优化这个问题，可以利用 前缀和 和 哈希表 来减少时间复杂度，从 O(N^2) 降到 O(N)。具体思路如下：

优化思路：

前缀和：用一个数组 prefix_sum 存储从数组起始到当前位置的累加和。对于任意两个位置 i 和 j（i <= j），子数组的和可以通过前缀和的差来计算：

$sum(A[i],A[i+1],...,A[j])=prefix\_sum[j]-prefix\_sum[i-1]$

如果 prefix_sum[j] - prefix_sum[i-1] 是 K 的倍数，那么 prefix_sum[j] % K == prefix_sum[i-1] % K(也就是说倍数减倍数也就是倍数少了几倍而已还是倍数)。
哈希表：通过哈希表记录每个前缀和的模 K 的出现次数。当计算到位置 j 时，检查当前 prefix_sum[j] % K 是否在哈希表中出现过。如果出现过，说明有一些区间的和是 K 的倍数。

算法实现：

使用一个哈希表 mod_count 来记录每个前缀和对 K 取模的结果出现的次数。
遍历数组时，计算当前的前缀和并取模，判断是否之前出现过相同的模值，若出现过，说明存在一个或多个区间的和是 K 的倍数。
对于每个 prefix_sum[j] % K，如果它在哈希表中已经存在，说明之前的某些前缀和与当前位置的前缀和之间的区间和是 K 的倍数。

代码解释：

输入：首先输入 n 和 k，然后读取数组 nums。
初始化：
- prefix_sum 用来存储当前的前缀和。
- mod_count 哈希表用于存储每个前缀和对 k 取模的结果及其出现次数。初始时 mod_count[0] = 1，因为一个前缀和为 0 的区间本身就符合条件。
遍历：
- 在遍历每个元素时，更新 prefix_sum，然后计算当前 prefix_sum % k。
- 如果该模值已经出现在哈希表中，说明存在从某个位置到当前的位置的子数组和是 k 的倍数。每次找到一个符合条件的模值，结果计数器 res 增加。
- 最后更新哈希表中该模值的计数。
输出：遍历结束后输出结果。

Java写法：

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 输入 N 和 Klong n = sc.nextLong();long k = sc.nextLong();// 存储输入的数列long[] nums = new long[(int) n];// 输入每个数字for (int i = 0; i < n; i++) {nums[i] = sc.nextLong();  }// 结果计数器long res = 0;  // 当前前缀和long prefixSum = 0;// 哈希表，用于存储 prefixSum % K 的计数  Map<Long, Long> modCount = new HashMap<>();  // 初始条件：前缀和为 0 时的模为 0，表示从数组开始到当前的子数组和为 K 的倍数modCount.put(0L, 1L);// 遍历数列for (int i = 0; i < n; i++) {// 更新前缀和prefixSum += nums[i];  // 计算当前前缀和对 K 的模long mod = prefixSum % k;// 如果当前 mod 在哈希表中出现过，则说明存在前缀和差为 K 的倍数的子数组if (modCount.containsKey(mod)) {// 增加结果计数，将其+1res += modCount.get(mod);  }// 更新当前 mod 的计数，将其+1modCount.put(mod, modCount.getOrDefault(mod, 0L) + 1);}// 输出结果System.out.println(res);  sc.close();}
}

C++写法：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;int main() {// 输入 N 和 Klong long n, k;cin >> n >> k;// 存储输入的数列vector<long long> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];  // 输入每个数字}long long res = 0;  // 结果计数器long long prefix_sum = 0;  // 当前前缀和unordered_map<long long, long long> mod_count;  // 哈希表，用于存储 prefix_sum % K 的计数// 初始条件：前缀和为 0 时的模为 0，表示从数组开始到当前的子数组和为 K 的倍数mod_count[0] = 1;// 遍历数列for (int i = 0; i < n; i++) {prefix_sum += nums[i];  // 更新前缀和// 计算当前前缀和对 K 的模long long mod = prefix_sum % k;// 如果 mod 为负数，调整为非负数（在 C++ 中，负数取模会得到负数）if (mod < 0) mod += k;// 如果当前 mod 在哈希表中出现过，则说明存在前缀和差为 K 的倍数的子数组if (mod_count.find(mod) != mod_count.end()) {res += mod_count[mod];  // 增加结果计数}// 更新当前 mod 的计数mod_count[mod]++;}cout << res << endl;  // 输出结果return 0;
}

这行代码：`modCount.put(0L, 1L);`

modCount.put(0L, 1L);

作用是在哈希表中初始化前缀和为 0 的情况，它表示从数组的开始位置到当前位置之间的子数组和恰好是 K 的倍数。为了理解为什么这么设置，可以从以下几个角度来解释：

1. 前缀和的含义：

前缀和 prefixSum[i] 是从数组起始位置到第 i 个元素的和。假设数组 nums 为 [A1, A2, ..., An]，那么前缀和是：

prefixSum[i] = A1 + A2 + ... + Ai

如果一个子数组 A[i, j] 的和是 K 的倍数，那么 prefixSum[j] - prefixSum[i-1] 必须是 K 的倍数。也就是说：

↓↓↓↓这里很重要↓↓↓↓

$(prefixSum[j] - prefixSum[i-1]) \% K == 0$

这等价于：

$prefixSum[j]\% K == prefixSum[i-1]\% K$

2. 初始化模值为 0：

假设我们从数组的开始位置就能够找到一个子数组和为 K 的倍数。为了方便这个情况的处理，我们需要在哈希表 modCount 中提前设置 modCount[0] = 1，表示前缀和为 0 时的模已经出现过一次。

为什么要设置为 1 呢？这表明如果我们在遍历过程中遇到一个前缀和的模值为 0，它意味着从数组的起始位置到当前位置之间的子数组和正好是 K 的倍数。这相当于一个“空的”子数组（从数组的开始位置到当前位置）的和是 K 的倍数。

3. 实际含义：

当遍历数组时，prefixSum[i] 表示当前数组从起始位置到第 i 个位置的元素和。
如果在某个位置 i，prefixSum[i] % K == 0，意味着从数组的第一个元素到当前元素的和就是 K 的倍数。因此，我们需要提前设定 modCount[0] = 1，表示从数组开始到当前子数组的和是 K 的倍数。

4. 避免漏掉边界情况：

例如，假设 nums = [5, 10, 15]，K = 5，此时从第一个元素到第三个元素的和 5 + 10 + 15 = 30 是 5 的倍数。如果没有 modCount[0] = 1 作为初始条件，我们可能会漏掉这个情况。

运行时间

时间复杂度和空间复杂度

时间复杂度：O(N)，遍历一次数组，每次操作都在常数时间内完成。
空间复杂度：O(K)，哈希表最多存储 K 个不同的模值。

总结

我们讲解了首先使用暴力的算法可以的一点分，但是对于N^5的数来说O(N^2)就无法通过全部的用例了，接下来介绍了如何通过使用前缀和与哈希表优化计算子数组和为 K 的倍数的个数问题，最终将时间复杂度从暴力解法的 O(N^2) 降到 O(N)，使得算法能够高效地处理大规模数据。

1. 题目描述

给定一个长度为 N 的数列，要求统计其中有多少个连续子数组，其和是 K 的倍数。数列和 K 的值都可能较大，因此不能采用暴力枚举的方式来解决。

2. 暴力解法

暴力解法的思路是：通过两层嵌套循环，遍历所有可能的子数组区间，计算每个子数组的和，并判断其是否为 K 的倍数。这种方式的时间复杂度为 O(N^2)，对于 N 最大可达 10^5 的情况，效率低下，不适用于大规模数据。

3. 优化思路：前缀和 + 哈希表

为了将暴力解法优化到 O(N)，可以利用前缀和与哈希表的组合。

前缀和的思想：

前缀和是指数组中从第 1 个元素到第 i 个元素的累加和。对于任意两个位置 i 和 j，prefixSum[j] - prefixSum[i-1] 即为 A[i] 到 A[j] 的子数组和。如果这个差值是 K 的倍数，那么 prefixSum[j] % K == prefixSum[i-1] % K。