查找數組，等於剩餘的元素的總和元素

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)。