查找数组中左侧之和等于右侧之和的元素

给定一个包含 n 个元素的数组，我们需要找到一个元素，该元素可以将数组分成两个部分，使得两个子数组的和相等。本质上，左侧的总和和右侧的总和等于该元素。如果不存在这样的元素，则返回 -1。

例如

数组={5,-1,4,6,12,0,-4}

在上面的数组中，元素 6 是将数组分成等和子数组的元素。

方法 1

解决问题的暴力方法是考虑每个元素作为分区元素，并计算左侧和右侧的和。如果和相等，则返回它。否则，移动到下一个元素。

Java 代码

输出

时间复杂度: O(N²)

空间复杂度：O(1)

方法 2

解决上述问题的优化方法是使用前缀和后缀数组来存储数组左侧和右侧的结果。

Java 代码

输出

时间复杂度: O(3*N)~ O(N)

空间复杂度: O(N+N)~O(N)

方法 3

我们可以使用恒定的空间来解决这个问题。我们将获取数组的总和并将其作为右侧总和，并将左侧总和初始化为零。现在，对于每个元素，我们将它视为一个分区元素，因此我们将从右侧总和中减去该元素的值，然后检查左侧总和和右侧总和。

如果两者相等，我们将更新结果。否则，我们将元素添加到左侧总和。

Java 代码

输出

说明

最初，我们有两个变量 left_sum 和 right_sum，它们都为零。我们将所有元素的总和存储在 right_sum 变量中，对于上面的示例，该值为 19。

现在当 i=0 时，我们将从 right_sum 中减去 arr[0]，以获得 arr[0] 右侧元素的总和。

因此 right_sum=17，left_sum =0。由于两者不相等，我们将继续前进，但在下一个值之前，当前值应添加到 left_sum。所以 left_sum =2。

对于 i=1，现在 right_sum=17，我们将减去 arr[1]，所以 right_sum=14，这是 arr[1] 右侧值的总和，而 left_sum=2，两者不相等，所以向前移动，在此之前将当前值添加到 left_sum。

所以 left_sum =5 且 right_sum=14。

对于 i=2，right_sum=14 - 4 = 10，left_sum = 5。两者不相等，所以 left_sum=5+4 = 9。

对于 i=3，right_sum=10-1 = 9，left_sum = 9，因为两者相同，而当前元素是我们的答案，所以我们将更新我们的结果。

result=arr[3]=1。

时间复杂度： O(N)

空间复杂度：O(1)

方法 4

我们可以使用双指针方法，但前提是元素必须是正数。我们将使用 i=0 和 j=n-1，并从左侧和右侧进行遍历。

• 如果 left_sum 和 right_sum 相等且 i<j，那么我们将 arr[i] 添加到 left_sum，将 arr[j] 添加到 right_sum，然后将 i 加一，将 j 减一。
• 如果 left_sum 和 right_sum 相等且 i==j，我们将结果存储为 arr[i]。
• 如果 left_sum<right_sum，那么我们将 arr[i] 添加到 left_sum 并将 i 加一。
• 如果 right_sum<left_sum，那么我们将 arr[j] 添加到 right_sum 并将 j 减一。

Java 代码

输出

时间复杂度： O(N)

空间复杂度：O(1)