一个算法题目给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/07/20 03:52:26

一个算法题目给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M
给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M
请给出思路.
不能用双层循环.

假设数组为a,有n个元素.
假设prefix[i]是a数组的前i个元素的和,令prefix[0] = 0.
如果prefix[j]%M == prefix[i]%M（其中0 <= j < i <= n）,则a[j+1 i]的和能被M整除.
于是对于每个i,可以用个表之类的数据结构快速找出它之前有多少个prefix[j]%M和prefix[i]%M相等,每次查找和更新的复杂度大约是O(1)的.
如果M比较小的话可以直接开个数组存之前prefix[j]%M出现了几次,复杂度是O(n + M)的.
如果M比较大,可以用二叉树或者哈希表存之前出现的prefix[j]%M出现了几次,因为这个值最多有O(n)种可能性,复杂度分别是O(n*log(n))和O(n)的.
如果需要记录有那些连续子数组,只要在表里记录一下有那些j就行了.

/* O(n + M)的算法 */
int work(vector<int> a, int M) {
    vector<int> b(M, 0);
    b[0] = 1;
    int prefix = 0, ans = 0;
    for (vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        prefix = (prefix + *it) % M;
        ans += b[prefix];
        b[prefix] += 1;
    }
    return ans;
}

编写一个函数,其功能是求给定数组中的最小值与最大值的元素数组中任选几个数相加,使其等于一个给定的值.请给出c++实现或者算法描述. 给定一个整数数组b[n],b中连续的相等元素构成的子序列称为平台.试设计算法,求出b中最长平台的长度. 把一个数组中每个元素后移m的算法 C语言：给定一个整形数组b[n],b中连续相等元素构成的子序列称为平台.编写程序,求出b中最长平台的长度. C语言,编辑一个函数fun统计给定数组中奇数和偶数的个数排列组合算法如何实现一维数组中元素的排列组合,并将其排列组合的所有情况输出?如：一个字符串数组 ABC；排列后输出：用VB编写一个程序,计算出给定的10*10矩阵（存放在二维数组A中）每行元素的最大值和每列元素的最小值给定数组a[0:n-1],试设计一个算法,在最坏情况下用3n/2-2次比较找出a[0:n-1]中元素的最大值和最求1 java算法一个数组中m个数(连续的) 需要分成n组求这n组的所有组合方式利用VB,编写一个3*4的二维数组输入任意整数,求所有数组元素和及平均值 matlab 编写一个m函数文件,求一数组中的元素,使得该元素的绝对值在该数组所有元素的绝对值中是最大的.

一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M

一个算法题目给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M