比較兩個數組的總和的快速算法？

Question

假設我有2個整數數組，它們可以不是相同的長度，任何索引的值都是有效的整數（min〜max）。如：

int data1[] = {1227210749, 382745290, 567552295, 1910060611, 
      577735884, 75518037, 742485551, 1202127013, 
      386030509, 308032134}; 

int data2[] = {1729472635, 1258098863, 259427472, 1664987257, 
      994376913, 1581883691, 1728724734, 2034013490}; 

我怎麼能快速比較他們知道哪一個有更大的總和？

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    // compares if the sum of data1 is bigger than sum of data2 
} 

Answer 1

顯而易見的方法是取兩個數組的總和，看看哪個更大。像這樣：

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    return (std::accumulate(a, a+len_a, 0) - std::accumulate(b, b+len_b, 0); 
} 

但是，這引入了整數溢出的可能性。這可以通過將最後一個參數accumulate更改爲0LL或0.0來避免。

Answer 2

直觀上（這是相當弱的我來說，我猜，我不的算法專家）這種感覺，就好像沒有在每個數字看一次，簡單地計算總和將是不可能的。這是因爲整數是有符號的，當添加任何元素時，數組的總和可以變爲0（或負數），所以你必須查看所有元素。

所以，儘量實現這樣的功能：

int int_array_sum(const int *array, size_t num_elements); 

然後簡單地調用每兩個陣列，並進行比較。

編輯：如在Tristan's answer中指出的那樣，當添加可能的大整數時存在溢出的風險。如果這是一個問題（這真的很適用於特定應用程序，也許溢出結果是「擁有更大總和」的一部分），您可以切換到更寬的整數類型，或者使用double。

Answer 3

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    long long sum_a = std::accumulate(a, a + len_a, 0ll); 
    long long sum_b = std::accumulate(b, b + len_b, 0ll); 

    return (sum_a < sum_b ? -1 : (sum_a == sum_b ? 0 : 1)); 
} 

Answer 4

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    double sum1=0; 
double sum2=0; 

for(int i=0;i<len_a;i++) 
sum1=sum1+a[i]; 

for(int i=0;i<len_b;i++) 
sum2=sum2+b[i]; 

if(sum1>sum2) 
return 1; 
else 
return 0; 

}