关于寻找最小平均的长度≥2子数组的编程问题优化求解问询

嘿，这个问题我之前琢磨过！咱们先明确需求：给定整数数组 [a₁,a₂,...,aₖ]，得找出一个长度至少为2的子数组，让它的平均值最小——也就是找到合适的起始索引i和子数组长度l≥2，使得(aᵢ + aᵢ₊₁ + ... + aᵢ₊ₗ₋₁)/l的值是全局最小的。

朴素的O(n²)暴力解法 #

最直接的思路就是硬撸所有可能的子数组：

• 挨个遍历每个起始位置i（从数组开头到倒数第二个元素，因为子数组至少要2个元素）
• 对每个起始点，再遍历所有可能的子数组长度l（从2到剩余元素个数）
• 计算每个子数组的和，除以长度得到平均值，全程记录最小的那个值和对应的子数组

这种方法逻辑简单，但时间复杂度是O(n²)，数组元素多了之后肯定会超时，得找更高效的路子。

关键洞察：最小平均值的子数组长度只能是2或3 #

这里的核心优化点就是：全局平均值最小的子数组，长度必然是2或者3。

为啥呢？咱们用反证法想一下：假设存在一个长度l≥4的子数组，它的平均值是全局最小的。那我们可以把这个长数组拆成两个更短的子数组（比如拆成一个长度2和一个长度l-2的子数组）。根据平均值的性质，这两个子数组里至少有一个的平均值小于等于原长数组的平均值。如果其中一个等于原平均值，那我们可以继续拆分，直到拆出长度为2或3的子数组；如果其中一个平均值更小，那原长数组就不可能是全局最小的，这就矛盾了。

所以啊，我们根本不用考虑长度≥4的子数组，只需要遍历所有长度为2和3的子数组，计算它们的平均值，找到最小的那个就行！

线性时间的实现思路 #

这样一来，我们只需要做两轮线性遍历：

1. 遍历所有相邻两个元素的组合（一共n-1个），计算它们的平均值
2. 遍历所有相邻三个元素的组合（一共n-2个），计算它们的平均值
3. 全程记录最小的平均值对应的子数组起始位置和长度

整个过程的时间复杂度就是O(n)，效率直接拉满。

伪代码示例 #

def find_min_avg_subarray(arr):
    n = len(arr)
    if n < 2:
        return None  # 数组长度不够，不符合题目要求
    min_avg = float('inf')
    best_start = 0
    best_length = 2

    # 检查所有长度为2的子数组
    for i in range(n - 1):
        current_avg = (arr[i] + arr[i+1]) / 2
        if current_avg < min_avg:
            min_avg = current_avg
            best_start = i
            best_length = 2

    # 检查所有长度为3的子数组
    for i in range(n - 2):
        current_avg = (arr[i] + arr[i+1] + arr[i+2]) / 3
        if current_avg < min_avg:
            min_avg = current_avg
            best_start = i
            best_length = 3

    # 返回最小平均值的子数组
    return arr[best_start : best_start + best_length]

这样就能高效解决这个问题啦！

内容的提问来源于stack exchange，提问作者Davide Spataro