TapeEquilibrium Problem in Java

这是许多顶级 IT 公司（如Google、Amazon、TCS、Accenture等）经常在面试中提出的问题。通过解决该问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将通过不同的方法和逻辑来解决 TapeEquilibrium 问题。我们还将为此创建 Java 程序。

TapeEquilibrium 问题是一项常见的算法挑战。它涉及在将数组按不同位置分割时，找到两部分之和的最小差值。

TapeEquilibrium 问题

一个由 N 个整数组成的非空零索引数组 A。数组 A 表示磁带上的数字。

任何整数 K，其中 0 < K < N，将该磁带分成两个非空部分

两部分之间的差值为

简单来说，就是数组 A 的第一部分之和与第二部分之和之间的差值。

该问题在于找到两个子数组的最小和。主要策略是先计算整个数组的总和，然后使用每个数组索引的运行总和来计算每个索引处两个子数组的总和。

任务是创建一个 Java 程序，其中包含一个非空零索引数组 A，包含 N 个整数，返回最小差值。

示例

考虑一个数组：A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

我们可以在四个地方分割这个磁带

K = 1, 差值 = |3 − 10| = 7

K = 2, 差值 = |4 − 9| = 5

K = 3, 差值 = |6 − 7| = 1

K = 4, 差值 = |10 − 3| = 7

在此示例中，最小差值为 1。

方法：暴力法

TapeEquilibrium 问题的暴力破解方法涉及计算数组每一次可能分割的左部和右部之和。它遍历所有可能的分割点，以找到两部分之间的最小差值。

算法

步骤 1：将 minDifference 设置为一个非常大的值（例如，Integer.MAX_VALUE）。

步骤 2：遍历从 1 到 n-1 的所有潜在分割点 i。

步骤 3：计算 leftSum（从数组开头到 i-1 的元素之和）。计算 rightSum（从 i 到数组末尾的元素之和）。

步骤 4：计算 leftSum 和 rightSum 之间的绝对差值。

步骤 5：如果当前差值较小，则更新 minDifference。

让我们在 Java 程序中实现上述方法。

输出

 
2000   

时间复杂度： O(N^2)

空间复杂度： O(1)

使用前缀和方法

前缀和方法计算一次数组的总和，然后利用该总和有效地确定每个分割点的左部和右部之和。它最大限度地减少了重复计算，提供了比暴力破解更有效的方法。

算法

步骤 1：计算数组中所有项的总和。

步骤 2：将 leftSum 设置为 0，将 minDifference 设置为 Integer.MAX_VALUE。

步骤 3：从索引 0 到 n-2 循环遍历数组。

步骤 4：对于每个索引，更新 leftSum 并计算 rightSum（totalSum - leftSum）。计算 leftSum 和 rightSum 之间的绝对差值。

步骤 5：如果当前差值较小，则更新 minDifference。

让我们在 Java 程序中实现上述方法。

输出

 
2000   

复杂度

时间复杂度：O(N)

空间复杂度： O(1)