Java 中最小差值子数组

我们给定一个输入数组 inputArr[]，其中包含 n 个数字。我们的任务是找到两个子数组之间的最小差值。子数组是从给定的输入数组中创建的。如果一个元素属于一个子数组，那么它就不能属于另一个子数组。此外，任何一个子数组都不能是空的。以下示例说明了这一点。

示例 1

输入

int arr[] = {7, 6, 8, 1, 5}

输出 1

解释： 如果我们创建两个子数组：subArr1 = {6, 8} 和 subArr2 = {7, 1, 5}，那么我们得到的子数组元素之和为：6 + 8 = 14，而 7 + 1 + 5 = 13，它们的差值为 14 - 13 = 1。因此，输出为 1。

示例 2

输入

int arr[] = {2, 4, 8, 9, 5, 7, 3, 6, 1}

输出 1

解释： 如果我们创建两个子数组：subArr1 = {8, 9, 5} 和 subArr2 = {2, 4, 7, 3, 6, 1}，那么我们得到的子数组元素之和为：8 + 9 + 5 = 22，而 2 + 4 + 7 + 3 + 6 + 1 = 23，它们的差值为 23 - 22 = 1。因此，输出为 1。

示例 3

输入

int arr[] = {3, 3, 3, 3, 3}

输出 3

解释： 如果我们创建两个子数组：subArr1 = {3, 3, 3} 和 subArr2 = {3, 3}，那么我们得到的子数组元素之和为：3 + 3 + 3 = 9，而 3 + 3 = 6，它们的差值为 9 - 6 = 3。因此，输出为 3。

方法：暴力法

我们将找到第一个子数组的所有可能值，对于每个可能的值，我们将找到第二个子数组的值。然后，我们将计算第一个子数组的值和第二个子数组的值之间的绝对差值，绝对最小值差就是我们的答案。下面的程序对此进行了说明。

文件名： MinDiffSubArrays.java

输出

For the input array: 
7 6 8 1 5 
The minimum difference between the two subarrays is: 1

For the input array: 
2 4 8 9 5 7 3 6 1 
The minimum difference between the two subarrays is: 1

For the input array: 
3 3 3 3 3 
The minimum difference between the two subarrays is: 3

复杂度分析： 每次递归调用都会产生两个指数级调用。因此，程序的 time complexity 是指数级的。

程序的 time complexity 太高，不适合较大的输入。因此，我们必须进行一些优化，这在以下方法中有所说明。

方法：使用前缀和 (PrefixSum)

借助一个辅助数组 (prefixArr[])，我们将存储输入数组 (inputArr[]) 的前缀和，其中 prefixArr[j] 表示从 0 到 j 的元素之和。

算法

步骤 1： 声明 prefixArr 数组以存储输入数组的前缀和。

步骤 2： 将输入数组的所有元素复制到 prefixArr 中。

步骤 3： 对于从 1 到 s - 1 的每个索引 j（s 是输入数组的大小），执行以下操作：

1. 将 prefixArr[j] 赋值为 prefixArr[j] + prefixArr[j - 1]。

步骤 4： 声明一个变量来存储最小差值，在本例中为 minDifference。

步骤 5： 声明一个变量来存储第一个子数组的元素之和，在本例中为 firstSubArrSum。

步骤 6： 声明一个变量来存储第二个子数组的元素之和，在本例中为 secondSubArrSum。

步骤 7： 将最大整数值赋给 minDifference 变量。

步骤 8： 对于索引 j 在 0 到 s - 2 的范围内，执行以下操作：

1. 将 firstSubArrSum 赋值为 prefixArr[j]。（第一个子数组的和）
2. 将 secondSubArrSum 赋值为 prefixArr[size of inputARr - 1] - prefixArr[j]。（第二个子数组的和）
3. 将 minDifference 赋值为 firstSubArrSum 和 secondSubArrSum 之间的绝对差值与 minDifference 的最小值。

步骤 9： 返回 minDifference 的值。

实施

观察上述算法的实现。

文件名： MinDiffSubArrays.java

输出

For the input array: 
7 6 8 1 5 
The minimum difference between the two subarrays is: 1

For the input array: 
2 4 8 9 5 7 3 6 1 
The minimum difference between the two subarrays is: 1

For the input array: 
3 3 3 3 3 
The minimum difference between the two subarrays is: 3

复杂度分析： findMinDiff() 方法使用了三个 for 循环。但是，它们之间没有嵌套。因此，time complexity 为 O(n)。此外，程序中还使用了辅助数组 (prefixArr[])，因此 space complexity 为 O(n)，其中 n 是输入数组中元素的总数。

我们将对 space complexity 进行优化。请参阅下面的方法。

方法：使用恒定空间 (Constant Space)

在此方法中，我们将使用变量而不是辅助数组。我们将使用一个变量 totalEleSum 来存储输入数组的所有元素之和。另一个变量 firstSubArrSum 也用于存储第一个子数组的元素之和。第二个子数组的元素之和可以通过 totalEleSum - firstSubArrSum 轻松计算得出。现在，进行比较以计算每个索引的绝对最小差值。请参阅以下程序。

文件名： MinDiffSubArrays.java

输出

For the input array: 
7 6 8 1 5 
The minimum difference between the two subarrays is: 1

For the input array: 
2 4 8 9 5 7 3 6 1 
The minimum difference between the two subarrays is: 1

For the input array: 
3 3 3 3 3 
The minimum difference between the two subarrays is: 3

复杂度分析： 该程序的 time complexity 与前一个程序相同。该程序的 space complexity 是恒定的，即 O(1)，因为程序没有使用辅助数组。