[LeetCode] 每日一题 2270. 分割数组的方案数
题目链接
题目描述
给你一个下标从 0 开始长度为 n
的整数数组 nums
。
如果以下描述为真,那么 nums
在下标 i
处有一个 合法的分割 :
前
i + 1
个元素的和 大于等于 剩下的n - i - 1
个元素的和。下标
i
的右边 至少有一个 元素,也就是说下标i
满足0 <= i < n - 1
。
请你返回 nums
中的 合法分割 方案数。
示例输入
示例 1
输入:nums = [10,4,-8,7]
输出:2
解释:
总共有 3 种不同的方案可以将 nums 分割成两个非空的部分:
- 在下标 0 处分割 nums 。那么第一部分为 [10] ,和为 10 。第二部分为 [4,-8,7] ,和为 3 。因为 10 >= 3 ,所以 i = 0 是一个合法的分割。
- 在下标 1 处分割 nums 。那么第一部分为 [10,4] ,和为 14 。第二部分为 [-8,7] ,和为 -1 。因为 14 >= -1 ,所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [10,4,-8] ,和为 6 。第二部分为 [7] ,和为 7 。因为 6 < 7 ,所以 i = 2 不是一个合法的分割。
所以 nums 中总共合法分割方案受为 2 。
示例 2
输入:nums = [2,3,1,0]
输出:2
解释:
总共有 2 种 nums 的合法分割:
- 在下标 1 处分割 nums 。那么第一部分为 [2,3] ,和为 5 。第二部分为 [1,0] ,和为 1 。因为 5 >= 1 ,所以 i = 1 是一个合法的分割。
- 在下标 2 处分割 nums 。那么第一部分为 [2,3,1] ,和为 6 。第二部分为 [0] ,和为 0 。因为 6 >= 0 ,所以 i = 2 是一个合法的分割。
提示
2 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
题解
解题思路
初始尝试:使用前缀和数组
一开始,我想到通过构造前缀和数组解决问题,具体实现如下:
class Solution {
public int waysToSplitArray(int[] nums) {
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1]; // 构造前缀和数组
}
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] >= nums[nums.length - 1] - nums[i]) {
count++; // 判断当前分割点是否满足条件
}
}
return count;
}
}
这个方法思路清晰,并且在大部分情况下表现良好。但是当数组元素较大时,由于整型溢出,导致部分测试用例无法通过。这让我意识到,前缀和数组不仅会修改原数组,还引入了额外的溢出风险
改进方法:动态维护总和与左部分和
经过进一步思考,我发现其实没有必要构造完整的前缀和数组。题目只需要比较左部分和与右部分和的大小,因此可以通过以下方式优化:
用一个变量
sum
记录数组的总和动态维护左部分的和
left
:从左到右遍历时累加当前元素值每次判断
left >= sum - left
是否成立
代码实现
class Solution {
public int waysToSplitArray(int[] nums) {
int count = 0;
long sum = 0; // 使用 long 类型防止溢出
for (int num : nums) {
sum += num; // 计算总和
}
long left = 0;
for (int i = 0; i < nums.length - 1; i++) {
left += nums[i]; // 维护左部分和
if (left >= sum - left) { // 判断是否满足条件
count++;
}
}
return count;
}
}
复杂度分析
时间复杂度:
第一次遍历计算数组总和,时间复杂度为 O(n)
第二次遍历判断合法分割点,时间复杂度为 O(n)
总时间复杂度为 O(n)
空间复杂度:
只使用常量级额外变量
sum
和left
,空间复杂度为 O(1)
总结
这道题让我意识到,解题时不能仅停留在常规思路上。当测试用例失败时,深入分析问题本质,往往可以找到更优的解法。通过从“前缀和数组”优化为“动态维护总和”,不仅避免了溢出问题,还让代码更加高效简洁。
这次经历还让我学到了以下几点:
不要盲目构造多余的数据结构:前缀和数组在这里其实并不是必要的
注意溢出风险:在处理大数问题时,要优先考虑数据类型的选择
优化方向源于需求:关注题目中实际需要的结果,尽量减少不必要的计算
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。