找出数组中有多少个子数组的和能够被给定数字整除。

Question

我卡在了一个算法问题上，请为下面的问题提供一些高效的算法。

问题是

找到和被给定数字整除的子数组数量。

我的工作

我编写了一个时间复杂度为O(N^2)的算法，其中N是数组的大小。

我的代码

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d", &T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d", &N);
        scanf("%d", &P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d", &val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%d\n%lld\n", k, answer);
    }
    return 0;
 }

- devsda

---

你所编写的代码究竟有什么问题？ - Kakalokia

我认为你的解决方案跳过了很多可能的组合... 除非这是你问题中“子数组”的定义方式，否则你只检查相邻元素的总和。 - Ashalynd

@Ashalynd，“子数组”通常指数组的连续部分（例如，“最大子数组问题”）。对于非连续部分，通常称为“子集”（例如，“子集和问题”）。 - Bernhard Barker

@Ashalynd 我已经考虑了所有情况，没有任何情况被遗漏。这里，“子数组”意味着连续的元素。 - devsda

Answer 1

对于给定的数字 X...

基本思路：（附带正确性的非正式证明）

如果范围 [a, b] 内所有数的和能够被 X 整除，则：

(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) % X

用更加通俗易懂的说法：

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

那么：

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

然后，如果右边的这两个和在除以X时余数相同，那么余数将会相互抵消，而两者之间的元素之和将能够被X整除。一个详细解释：

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

现在我们可以将B转换为形式PX + Q，将A转换为形式RX + S，其中P、Q、R和S是一些整数，且0 <= Q, S < X。根据定义，这里的Q和S分别是B和A除以X所得的余数。

因此，我们有：

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

显然，(P-R)X是X的倍数（结果就是(P-R)）。现在我们只需要Q-S也是X的倍数，但是由于0 <= Q，S < X，它们必须相等。

例子：

令B = 13，A = 7，X = 3。

这里B % X = 1，A % X = 1。

我们可以将B重写为4*3 + 1，将A重写为2*3 + 1。

然后C = 4*3 + 1 - 2*3 - 1 = 2*3，它是3的倍数。

高级思路：

构建一个哈希映射key->value，其中每个值表示从数组开头开始并以某个给定位置结束的可能性有多少种，这些可能性加起来sum mod X = key（请参见下面示例中的“Mod 3”行和地图值）。

现在，根据上面的逻辑，我们知道如果两个子数组从开头开始并在位置a和b结束，它们都具有相同的sum mod X，那么子数组[a，b]将可以被X整除。

因此，哈希映射中的每个值表示可能的起点和终点集合的大小，这将给我们一个可被X整除的子数组（任何点都可以是起点或终点）。

选择这些起始和结束点的可能方法数量简单地为
value choose 2 = value!/(2*(value-2)!)（如果value为1，则为0）。

因此，我们计算哈希映射中每个值，并将它们全部添加起来，以获得可被X整除的子数组数量。

算法：

构建一个哈希映射，其中将迄今为止的所有数字的累积总和mod X映射到该余数值出现的次数（预期的O(n)构造）。

将0的值增加1-这对应于数组的开始。

将计数器初始化为0。

对于哈希映射中的每个值，将value!/(2*(value-2)!)添加到计数器中。

计数器是所需的值。

运行时间：

预期O(n)。

例子：

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

子数组将是:

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0

- Bernhard Barker

---

你只考虑了连续的元素，而问题要求的是子数组的数量，我理解为子序列的形式而不是子字符串的格式，例如你没有考虑3+2+1或0+3+2+1，顺便说一下，我不知道保留顺序是否重要，例如我不知道我们应该计算3+2+1六次还是只计算一次（我想后者是可以接受的）。 - Saeed Amiri

@SaeedAmiri 中文中，“子数组”通常指数组的连续部分，例如“最大子数组问题”（http://en.wikipedia.org/wiki/Maximum_subarray_problem）。 - Bernhard Barker

不是这样的，比如在你的示例问题语句中非常明确地说明了“连续子数组”，而问题名称是通用的（应该要简短），因此在问题名称中不需要写出所有的细节。在这个问题定义中也没有关于连续性的讨论。因此我们应该假设它不是连续的。 - Saeed Amiri

@SaeedAmiri 好吧，无论如何，OP刚刚澄清它是连续的元素。 - Bernhard Barker

@Dukeling，我理解你解决这个问题的方式。但是我没有感觉到它的实现过程。你能否请解释一下，你是如何从最基本的步骤开始构建这个逻辑的呢？提前感谢。 - devsda

Answer 2

我可能有一个更简单的解决方案，时间复杂度为O(n)，空间复杂度为O(n+k)，其中n是数组大小，k是我们要检查可除性的数字。

将数组视为A[n]，数字为K。

1. 创建另一个数组SUM_TILL_NOW[n]。 2. 对于每个A[i]，填充SUM_TILL_NOW [i]= SUM_TILL_NOW[i-1]+A[i] %K; (SUM_TILL_NOW[0]= A[0]) 3. 找到在这个新数组中相等的两个数字。

为此，创建大小为K的新数组CHECK[]。

遍历SUM_TILL_NOW数组，检查是否设置了CHECK[SUM_TILL_NOW[i]]。

如果没有设置，则将其设置为i。

否则，CHECK[SUM_TILL_NOW[i]]，i是总和可被K整除的子集。

下面是同样的C++函数。

#include <iostream>
#include <string.h>

using namespace std;

void printrange(int* A, int N, int K)
{
    int STN[N], C[K];
    memset(C, -1, K*sizeof(int));
    int i;
    int sum=A[0];
    STN[0]= (A[0]%K);
    for (i= 1; i< N; i++)
    {
        sum+= A[i];
        STN[i]= sum%K;
    }
    for(i=0; i< N; i++)
    {
        if(C[STN[i]] == -1)
            C[STN[i]] =i;
        else
        {
            cout<< C[STN[i]]+1 <<" "<< i;
            break;
        }
    }
}

int main()
{
    int A[]= {6, 9, 2, 1, 8, 6, 2, 5};
    printrange(A, sizeof(A)/sizeof(A[0]), 7);
    return 0;
}

- Rohit Kalhans