查找数组，等于剩余的元素的总和元素

Question

我试图想到一个高效的算法，解决了以下问题：

鉴于整数数组，返回元素的索引该数组等于数组中其余元素的总和;如果不存在这样的元素，则返回-1。

例如，给定的[1,2,3,6]阵列，然后返回4，因为给定的6=1+2+3;[3, -3, 5, 1]，由于3 = -3 + 5 + 1返回0。

有什么想法？

Answer 1

在两个运行解决这个问题：

• 在第一次运行的阵列
• 在第二次运行中创建的所有整数的总和，检查每个元件i，arrSum == i * 2是否持有 - 等同于arrSum - i == i 。如果它成立，你已经找到了你的搜索元素。

在代码：

int sum = 0; 
for(int i : arr) 
    sum += i; 

for(int i = 0 ; i < arr.length ; i++) 
    if(sum == arr[i] * 2) 
     return i; 

return -1; 

在奔跑O(n)。