文章

[LeetCode] 每日一题 2270. 分割数组的方案数

题目链接

https://leetcode.cn/problems/number-of-ways-to-split-array

题目描述

给你一个下标从 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;
    }
}

这个方法思路清晰,并且在大部分情况下表现良好。但是当数组元素较大时,由于整型溢出,导致部分测试用例无法通过。这让我意识到,前缀和数组不仅会修改原数组,还引入了额外的溢出风险

改进方法:动态维护总和与左部分和

经过进一步思考,我发现其实没有必要构造完整的前缀和数组。题目只需要比较左部分和与右部分和的大小,因此可以通过以下方式优化:

  1. 用一个变量 sum 记录数组的总和

  2. 动态维护左部分的和 left:从左到右遍历时累加当前元素值

  3. 每次判断 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;
    }
}

复杂度分析

  1. 时间复杂度

    • 第一次遍历计算数组总和,时间复杂度为 O(n)

    • 第二次遍历判断合法分割点,时间复杂度为 O(n)

    • 总时间复杂度为 O(n)

  2. 空间复杂度

    • 只使用常量级额外变量 sumleft,空间复杂度为 O(1)

总结

这道题让我意识到,解题时不能仅停留在常规思路上。当测试用例失败时,深入分析问题本质,往往可以找到更优的解法。通过从“前缀和数组”优化为“动态维护总和”,不仅避免了溢出问题,还让代码更加高效简洁。

这次经历还让我学到了以下几点:

  1. 不要盲目构造多余的数据结构:前缀和数组在这里其实并不是必要的

  2. 注意溢出风险:在处理大数问题时,要优先考虑数据类型的选择

  3. 优化方向源于需求:关注题目中实际需要的结果,尽量减少不必要的计算

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0