作业帮一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M请给
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/29 04:36:45
一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M请给
一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M
给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M
请给出思路.
不能用双层循环.
一个算法题目 给定一个数组其每个元素都是正数,和一个给定值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;
}