一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M请给
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/06 19:34:12
![一个算法题目 给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M给定一个数组其每个元素都是正数,和一个给定值M,求所有连续的子数组其和可以整除M请给](/uploads/image/z/14721349-13-9.jpg?t=%E4%B8%80%E4%B8%AA%E7%AE%97%E6%B3%95%E9%A2%98%E7%9B%AE+%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%95%B0%E7%BB%84%E5%85%B6%E6%AF%8F%E4%B8%AA%E5%85%83%E7%B4%A0%E9%83%BD%E6%98%AF%E6%AD%A3%E6%95%B0%2C%E5%92%8C%E4%B8%80%E4%B8%AA%E7%BB%99%E5%AE%9A%E5%80%BCM%2C%E6%B1%82%E6%89%80%E6%9C%89%E8%BF%9E%E7%BB%AD%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84%E5%85%B6%E5%92%8C%E5%8F%AF%E4%BB%A5%E6%95%B4%E9%99%A4M%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%95%B0%E7%BB%84%E5%85%B6%E6%AF%8F%E4%B8%AA%E5%85%83%E7%B4%A0%E9%83%BD%E6%98%AF%E6%AD%A3%E6%95%B0%2C%E5%92%8C%E4%B8%80%E4%B8%AA%E7%BB%99%E5%AE%9A%E5%80%BCM%2C%E6%B1%82%E6%89%80%E6%9C%89%E8%BF%9E%E7%BB%AD%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84%E5%85%B6%E5%92%8C%E5%8F%AF%E4%BB%A5%E6%95%B4%E9%99%A4M%E8%AF%B7%E7%BB%99)
一个算法题目 给定一个数组其每个元素都是正数,和一个给定值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;
}