Java Program to Find the Minimal Average of Any Slice Containing at Least Two Elements

这是像Google、Amazon、TCS、Accenture等顶级 IT 公司面试中经常遇到的问题。通过解决这个问题，可以考察求职者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将通过不同的方法和逻辑来查找包含至少两个元素的任意切片的最小平均值。此外，我们还将为此创建 Java 程序。

查找包含至少两个元素的任意切片的最小平均值的问题被称为MinAvgTwoSlice 问题，并且是流行算法任务之一。数组中的切片是子数组，因此需要找到平均值最小的切片。

问题陈述

给定一个包含 n 个整数的数组，问题是给定两个 n 个整数的序列，找到平均值最小的切片的起始位置。切片至少需要包含两个元素。如果有两个或更多切片具有相同的最小平均值，则应返回第一个切片的位置。

关键观察

小切片很重要：可以注意到，切片的最小平均值要么是两个元素的切片，要么是三个元素的切片。这意味着包含这些最小切片的实际切片将不会具有比最小切片“平均值”更低的值。

证明：如果切片的大小大于三，则可以始终比较平均值，并且可以将切片分解为更小的切片。此外，检查大小为二或三的切片就足够了，因为彼此距离较远的元素不会影响概率。

效率：只检查大小为二或三的切片，就有可能达到线性时间复杂度的有效解决方案。

输出

 
The starting position of the minimal average slice is: 1   

时间复杂度：O(n)，其中变量 n 表示数组的大小。因为它只需要遍历数组四次，并在每次遍历中比较大小为 2 和 3 的子数组。

空间复杂度：由于添加了几个额外的 变量，空间复杂度保持为 O(1)。

解释

两个元素的切片

我们使用循环遍历数组，并使用整数除法找到数组中每两个相邻元素的平均值。每当我们评估 a[] 的新最小平均值时，我们使用的 minAvg 和 minIndex 都会相应更新。

三个元素的切片

同样，我们监控连续三个项的平均值是否相等。这样，我们就确保不会跳过任何潜在的最小平均值。

为什么大小为 2 和 3 就足够了？

两个元素的切片：在这种情况下，如果存在于最小切片中，则平均值也会被指示。因此，两个元素的切片提供了表中两个元素的快速对比。

三个元素的切片：添加一个额外的元素是可能的，因为它可能证明平均值比之前显示的小，如果那个元素显着降低了所引用的平均值。因为检查了大小为 3 的切片。其思想是确定大小为 3 的取货车是否合适。

注意事项和边缘情况

数组大小：该函数适用于大小大于 2 的数组。如果数组大小为 2，则唯一可以形成的切片是整个数组。

负数：解决方案也能很好地处理负数，因为正如我提到的，平均值是使用浮点值计算的。

所有元素相同：如果所有元素都相同，则最小平均值切片可以从任意位置开始；但是，给定的 函数将返回第一个。

结论

可以随机检查大小为 2 或 3 的切片，以便在大多数情况下它们的平均值大于将其他任何元素添加到该切片的平均值。因此，当我们只关心最小平均值时，检查大小为 4 的切片是毫无意义的。这就是为什么解决方案将仅构建和关注大小为 2 和 3 的切片，以确保其准确性和实用性。