查找一個數組的子數組，其數目除以給定的數字

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; 
} 

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)!)（如果值爲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 

Answer 2

我可以具有簡單的解決方案。在O（n）時間和O（n + k）空間中。其中n是數組的大小& k是我們正在檢查可分性的數字。

考慮數組作爲A [n]和數量爲K

1. 創建另一個陣列SUM_TILL_NOW [N]。對於每個A [i]填充SUM_TILL_NOW [i] = SUM_TILL_NOW [i-1] + A [i]％K; （SUM_TILL_NOW [0] = A [0]）
2. 在這個新數組中找到兩個相等的數字。

爲此創建新陣列CHECK []大小的K.

迭代的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; 
}