📍前言
本篇将学习前缀和OJ题和可被 K 整除的子数组相关知识。
持续更新中~
【前缀和】974. 和可被 K 整除的子数组
问题描述
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空）子数组 的数目。子数组是数组的连续部分。
知识点
-
子数组问题
子数组问题：
在计算机科学和编程中，子数组问题是一类涉及从给定数组中选择连续元素并形成新数组的问题。这类问题通常要求找到满足特定条件的子数组，例如最大和子数组、最长递增子数组等。子数组问题可以通过动态规划、滑动窗口等方法来解决。
-
同余定理
同余定理：
同余定理是数论中的一个基本概念，用于描述整数间的关系。给定两个整数a和b以及模数m，如果满足a - b是m的整数倍，即(a - b) % m = 0，则称a和b对于模数m是同余的。在这种情况下，我们写做a ≡ b (mod m)。同余定理在数论、密码学和计算机科学等领域都有广泛应用。
例如，考虑模数m = 5，我们有以下同余关系：
10 ≡ 5 (mod 5)
15 ≡ 0 (mod 5)
-5 ≡ 0 (mod 5)
20 ≡ 0 (mod 5)
在这些例子中，每个数都与0保持相同的模5余数，因此它们是同余的。
思路
这段代码是一个C++实现的函数，用于计算一个整数数组中可以被k整除的子数组数量。思路如下：
-
定义常量
maxn为30001，用于限制数组大小，同时初始化整数数组sum和h。 -
定义名为
subarraysDivByK的函数，该函数接收一个整数数组nums，数组的长度numsSize以及一个整数k作为参数。 -
初始化变量
ans为0，用于存储满足条件的子数组数量。同时，使用memset函数将h数组初始化为0。 -
计算前缀和数组
sum。遍历数组nums，对于每个元素nums[i]，计算sum[i]为sum[i-1]与nums[i]之和除以k的余数。如果余数是负数，将其调整为正数。 -
初始化
h[0]为1，用于存储前缀和为0的子数组数量。 -
遍历数组
nums，对于每个元素nums[j]，执行以下操作：
-
将当前前缀和
sum[j]添加到结果ans中，即ans加上h[sum[j]]的值。 -
更新
h数组中对应前缀和的数量，即将h[sum[j]]加1。
- 返回结果
ans，表示满足条件的子数组数量。
代码实现
#define maxn 30001
int sum[maxn];
int h[maxn];
int subarraysDivByK(int* nums, int numsSize, int k){
int ans=0;
memset(h,0,sizeof(h));
sum[0]=nums[0]%k;
if(sum[0]<0)sum[0]+=k;
for(int i=1;i<numsSize;++i)
{
sum[i]=(sum[i-1]+nums[i])%k;
if(sum[i]<0)sum[i]+=k;
}
h[0]=1;
for(int j=0;j<numsSize;++j)
{
ans+=h[sum[j]];
h[sum[j]]++;
}
return ans;
}
题目总结
本题主要考察了子数组问题以及同余定理的应用。通过计算前 i 个元素的和模 k 的结果，可以快速判断出是否存在满足条件的子数组。同时，使用一个数组 h 记录模 k 的结果出现的次数，可以优化时间复杂度，提高解题效率。