algorithm - 在数组中找到等于剩余元素之和的元素

Question

我在想一个解决以下问题的有效算法:

给定一个整数数组，返回数组中等于数组中剩余元素之和的元素的索引；如果不存在这样的元素，则返回 -1。

例如，给定数组[1,2,3,6]，则返回4，因为6=1+2+3;给定 [3, -3, 5, 1]，返回 0，因为 3 = -3 + 5 + 1。

有什么想法吗？

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) 中运行。