蓝桥杯真题——k倍区间

暴力解法：通过两层嵌套循环，遍历所有可能的子数组区间 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 和 K
    long 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 和 K
        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;  
        // 当前前缀和
        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)) {
                // 增加结果计数，将其+1
                res += modCount.get(mod);  
            }

            // 更新当前 mod 的计数，将其+1
            modCount.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 和 K
    long 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。

使用哈希表：

我们通过一个哈希表 mod_count 来记录每个前缀和对 K 取模的结果出现的次数。每次计算新的前缀和时，查看是否存在相同的模值，若存在，说明从某个位置到当前的位置之间的子数组和是 K 的倍数。

关键点：

咱就是说：

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

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

这等价于：

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

原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/143746397

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：鸿蒙next版开发：相机开发-元数据(ArkTS)
下一篇：go语言的面向对象详解

论文《基于现实迷宫地形的电脑鼠设计》深度分析（二）——超声波环境感知算法
《基于现实迷宫地形的电脑鼠设计》是由吴润强、庹忠曜、刘文杰、项璟晨、孙科学等人于2023年发表的一篇优秀期刊论文。其针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题，特基于超声波测距与传统迷宫算
阅读更多2024-11-18
笔记整理—linux驱动开发部分（13）块设备
整理一下学习的内容，个人观点可能存在错误。本章介绍了什么是块设备，对比了块设备与字符设备的区别，并说明块设备更适合驱动内存类设备的原因。
阅读更多2024-11-18
【Linux】进程状态，优先级，环境变量
进程状态，优先级，环境变量
阅读更多2024-11-18
【Spring】循环引用解决流程，只用一二级缓存？
循环依赖：循环依赖其实就是循环引用，也就是bean互相持有对方，最终形成闭环。比如A依赖于B，B依赖于A循环依赖在spring中是允许存在，spring框架依据三级缓存已经解决了大部分的循环依赖三级缓
阅读更多2024-11-18
Windows、Linux多系统共享蓝牙设备
不需要配对的其实非常不可靠，单独使用可能感受不到，当在很近的距离内使用多套无线鼠标或者无线话筒，就会发现相互干扰的现象，因为它们都是基于一个简单的标签或者信道来区分，而这种划分很容易重复。在网上查资料
阅读更多2024-11-18
自然语言处理技术之细粒度实体识别
细粒度实体识别是自然语言处理（NLP）领域中的一个重要研究方向，其目标是从文本中识别出更加具体和详细的实体类型。相比于传统的实体识别（NER），细粒度实体识别不仅关注常见的实体类别（如。
阅读更多2024-11-18
Linux 域通信
【代码】Linux 域通信。
阅读更多2024-11-18
正则表达式从入门到精通
正则表达式从入门到入土
阅读更多2024-11-18
linux alsa-lib snd_pcm_open函数源码分析（四)
alsa源码分析
阅读更多2024-11-18
算法日记 26-27day 贪心算法
贪心算法
阅读更多2024-11-18

蓝桥杯真题——k倍区间

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

题目描述

输入描述

输出描述

输入输出样例

示例

运行限制

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

思路：

具体流程：

优缺点：

Java写法：

C++写法：

AC情况

时间复杂度和空间复杂度

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

优化思路：

算法实现：

代码解释：

Java写法：

C++写法：

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

1. 前缀和的含义：

2. 初始化模值为 0：

3. 实际含义：

4. 避免漏掉边界情况：

运行时间

时间复杂度和空间复杂度

总结

1. 题目描述

2. 暴力解法

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

前缀和的思想：

使用哈希表：

关键点：

相关文章

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