c – 查找数组的子数组,其数量除以给定数字

概述我遇到了一个算法问题.请为我提出一些针对以下问题的有效算法. 问题是 查找数量的子数组,其总和可以被给定的数字整除. 我的工作 我做了一个算法,其复杂度为O(N ^ 2),这里,N =数组的大小. 我的守则 #include<stdio.h>using namespace std; main() { int N; int P; int T; int val; 我遇到了一个算法问题.请为我提出一些针对以下问题的有效算法.

问题是

查找数量的子数组,其总和可以被给定的数字整除.

我的工作

我做了一个算法,其复杂度为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; }

解决方法 对于给定的数字X ……

基本思路:(具有正确性的非正式证明)

如果[a,b]范围内的数字之和可被X整除,则：

(Σi= 1到a-1input [i])％X =(Σi= 1到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 twoB = the sum from the first element to bA = 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 - SC = PX - RX + Q - SC = (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整除. 高级方法： 构造密钥的哈希映射 – > value,其中每个值表示从数组的开头可以开始的方式,并在某个给定位置结束,加起来为sum mod X = key(请参阅下面示例中的“Mod 3”行和地图值) ).

现在,基于上面的逻辑,我们知道如果两个子阵列从开始开始并分别在位置a和b结束,两者具有相同的和模x,则子阵列[a,b]将被X整除.

因此,散列图中的每个值表示一组可能的起点和终点的大小,这将给我们一个可被X整除的子阵列(任何点都可以是起点或终点).

选择这些起点和终点的可能方式很简单
value choose 2 = value!/(2*(value-2)!)(如果值为1则为0).

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

算法：

构造一个哈希映射,它将存储到目前为止所有数字的累积和,映射到该剩余值出现的频率计数(在预期的O(n)中构造).

将0的值增加1 – 这对应于数组的开始.

将计数初始化为0.

对于散列映射中的每个值,将值！/(2 *(value-2)！)添加到计数中.

计数是期望值.

运行时间：

预期O(n).

例：

input:    0  5  3  8  2  1X = 3Sum:   0  0  5  8 16 18 19Mod 3: 0  0  2  2  1  0  1Map:  0 -> 3  1 -> 2  2 -> 2Count = 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

总结

以上是内存溢出为你收集整理的c – 查找数组的子数组,其数量除以给定数字全部内容，希望文章能够帮你解决c – 查找数组的子数组,其数量除以给定数字所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。