比较两个数组的总和的快速算法？

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; 

}