数组边界和与内部和问题的优化解法

1. 问题背景与定义

今天遇到一个有趣的数组处理问题：给定一个整数数组capacity，要求找出所有满足"边界和等于内部和"的子数组。这类问题在实际业务场景中经常出现，比如资源分配校验、数据完整性检查等场景。

边界和指的是子数组第一个和最后一个元素的和，内部和则是去掉首尾元素后剩余元素的和。例如对于子数组[1,2,3,4]，边界和是1+4=5，内部和是2+3=5，这个子数组就满足条件。

2. 问题分析与解法思路

2.1 暴力解法分析

最直观的解法是暴力枚举所有可能的子数组，然后逐个计算边界和与内部和进行比较。对于一个长度为n的数组，子数组数量是O(n²)级别，每个子数组的计算是O(n)时间复杂度，因此总时间复杂度是O(n³)。

python复制def find_subarrays_brute_force(capacity):
    result = []
    n = len(capacity)
    for i in range(n):
        for j in range(i+1, n):
            boundary = capacity[i] + capacity[j]
            interior = sum(capacity[i+1:j])
            if boundary == interior:
                result.append(capacity[i:j+1])
    return result

这种解法在小规模数据上可行，但当n较大时（比如n>1000），性能会急剧下降。

2.2 优化思路：前缀和技巧

观察到内部和的计算可以优化。我们可以预先计算前缀和数组prefix，其中prefix[i]表示前i个元素的和。这样任意子数组capacity[i..j]的内部和可以表示为：

interior_sum = prefix[j] - prefix[i+1]

这样就把内部和的计算从O(n)降到了O(1)。结合这个优化，总时间复杂度可以降到O(n²)。

python复制def find_subarrays_optimized(capacity):
    result = []
    n = len(capaci