Question

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

给定一个数组其每个元素都是正数，和一个给定值M，求所有连续的子数组其和可以整除M
请给出思路。
补充一下 不能用双层循环。。

Answer 1

假设数组为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;
}