LeetCode 3637题解：单次线性扫描实现三段式数组分割-平芜编程栈

1. 问题背景与题目解析

今天我们来拆解LeetCode第3637题"三段式数组I"的第一种解法——单次线性扫描。这是一道典型的数组操作题目，在最近的周赛中出现频率较高，考察我们对数组遍历和边界条件处理的掌握程度。

题目描述是这样的：给定一个整数数组nums，我们需要判断它是否可以被分成三个连续的非空子数组，使得第一个子数组的和等于第三个子数组的和，且第二个子数组的和等于它们的和。换句话说，寻找索引i和j（1 ≤ i < j < nums.length-1），使得：

sum(nums[0..i]) == sum(nums[j+1..n-1])
sum(nums[i+1..j]) == sum(nums[0..i])

举个例子，对于数组[1,2,1,2,1]，我们可以选择i=1和j=3：

第一部分[1,2]和为3
第二部分[1]和为1
第三部分[2,1]和为3 这不满足条件。但如果选择i=1和j=2：
第一部分[1,2]和为3
第二部分[1]和为1
第三部分[2,1]和为3 仍然不满足。实际上这个数组没有解。

而数组[1,3,1,1,1]在i=1,j=3时：

[1,3]=4
[1]=1
[1,1]=2 也不满足。但i=1,j=2时：
[1,3]=4
[1]=1
[1,1]=2 依然不满足。看来这道题比表面看起来要复杂。

2. 暴力解法与初步优化

最直观的解法是暴力枚举所有可能的i和j组合，然后计算三个子数组的和进行比较。这种方法的时间复杂度是O(n^3)，对于较大的数组显然不可行。

我们可以先进行一些优化。首先预处理前缀和数组prefix，其中prefix[i]表示nums[0..i-1]的和。这样计算任意子数组的和可以在O(1)时间内完成。优化后的暴力解法如下：

def threeParts(nums): n = len(nums) prefix = [0] * (n + 1) for i in range(n): prefix[i+1] = prefix[i] + nums[i] for i in range(1, n-1): for j in range(i+1, n-1): sum1 = prefix[i] - prefix[0] sum2 = prefix[j] - prefix[i] sum3 = prefix[n] - prefix[j] if sum1 == sum3 and sum2 == sum1: return True return False

这个解法将时间复杂度降到了O(n^2)，但对于n=10^5的情况仍然不够高效。我们需要更聪明的办法。

3. 单次线性扫描解法

观察题目条件，我们可以发现一些关键性质：

整个数组的总和sum_all = sum1 + sum2 + sum3
根据条件sum1 = sum3，sum2 = sum1
因此sum_all = 3*sum1

这意味着整个数组的和必须是3的倍数，否则直接返回False。这给了我们一个强有力的剪枝条件。

基于这个观察，我们可以设计一个线性扫描算法：

首先计算整个数组的总和sum_all
如果sum_all % 3 != 0，直接返回False
否则，目标sum_target = sum_all // 3
我们需要找到两个位置i和j，使得：
- 前缀到i的和为sum_target
- 前缀到j的和为2*sum_target
- 且i和j之间有至少一个元素(j ≥ i+2)

具体实现时，我们可以：

从左到右扫描数组，累加当前和curr_sum
当curr_sum == sum_target时，记录第一个分割点i
当curr_sum == 2*sum_target时，记录第二个分割点j
确保i和j都存在且i < j

以下是Python实现：

def threeParts(nums): sum_all = sum(nums) if sum_all % 3 != 0: return False target = sum_all // 3 n = len(nums) curr_sum = 0 i, j = -1, -1 for idx in range(n): curr_sum += nums[idx] if curr_sum == target and i == -1: i = idx elif curr_sum == 2 * target and i != -1 and idx < n - 1: j = idx return True return False

这个算法只需要一次线性扫描，时间复杂度O(n)，空间复杂度O(1)，非常高效。

4. 边界条件与测试用例

在实现这类数组分割问题时，特别需要注意边界条件。让我们考虑几个关键测试用例：

最小长度数组：
- [1,1,1] → True (i=0,j=1)
- [1,2,1] → False
全零数组：
- [0,0,0,0,0] → True (任何i,j都满足)
无法三等分：
- [1,2,3,4,5] → False (sum=15,但无法分割)
多个可能分割点：
- [1,0,1,0,1] → True (i=1,j=3或i=2,j=3)
大数测试：
- [1000000000]*10000 → 需要考虑数值溢出问题

在实现时，我们还需要注意：

数组长度至少为3
分割点i和j不能重合
最后一个子数组不能为空

5. 算法优化与变种

这个线性扫描算法已经很高效，但还可以做一些优化：

提前终止：当找到j后可以立即返回，不需要继续扫描
反向扫描：也可以从右向左扫描，寻找sum_target和2*sum_target
双指针法：维护两个指针分别寻找第一个和第二个分割点

对于类似的数组分割问题，这个思路可以推广。例如：

判断数组能否分成两部分等和 → 寻找sum_all/2
判断数组能否分成k部分等和 → 寻找sum_all/k的倍数点

这类问题的核心都是：

通过总和判断可能性
通过前缀和定位分割点
线性扫描实现高效求解

6. 实际应用与扩展

这种数组分割问题在实际中有许多应用场景：

负载均衡：将任务分成多个部分均匀分配
文件分割：大文件分块处理
数据分析：将数据集分成训练集、验证集和测试集

对于更复杂的情况，比如：

不均匀分割（比例不同）
多维数组分割
带权重的分割

我们可以基于类似的思路进行扩展，结合动态规划等其他算法技巧。

7. 代码实现细节与调试技巧

在实际编码时，有几个容易出错的地方需要注意：

索引处理：Python是0-based索引，要确保分割点在合法范围内
整数除法：使用//而不是/，避免浮点数问题
空子数组：确保每个子数组至少有一个元素
大数处理：对于特别大的数，考虑使用long类型

调试时可以：

打印中间变量（curr_sum, i, j）
使用小测试用例手动验证
检查边界条件（空数组、最小数组等）

一个更健壮的实现可能包括：

def threeParts(nums): if len(nums) < 3: return False sum_all = sum(nums) if sum_all % 3 != 0: return False target = sum_all // 3 curr_sum = 0 count = 0 for num in nums[:-1]: # 确保最后一个子数组非空 curr_sum += num if curr_sum == target * (count + 1): count += 1 if count == 2: return True return False

这个版本通过计数的方式更清晰地表达了我们要找两个分割点的意图。