Medium

题目描述

给你一个下标从 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] 和 [4,-8,7] 。前一部分的和为 10 ，后一部分的和为 3 。因为 10 >= 3 ，所以 i = 0 是一个有效的分割。
- 在下标 1 处分割 nums ，得到 [10,4] 和 [-8,7] 。前一部分的和为 14 ，后一部分的和为 -1 。因为 14 >= -1 ，所以 i = 1 是一个有效的分割。
- 在下标 2 处分割 nums ，得到 [10,4,-8] 和 [7] 。前一部分的和为 6 ，后一部分的和为 7 。因为 6 < 7 ，所以 i = 2 不是一个有效的分割。
因此，nums 中有效分割的方案数为 2 。

示例 2：

输入：nums = [2,3,1,0]
输出：2
解释：
共有 2 个 nums 的有效分割：
- 在下标 1 处分割 nums ，得到 [2,3] 和 [1,0] 。前一部分的和为 5 ，后一部分的和为 1 。因为 5 >= 1 ，所以 i = 1 是一个有效的分割。
- 在下标 2 处分割 nums ，得到 [2,3,1] 和 [0] 。前一部分的和为 6 ，后一部分的和为 0 。因为 6 >= 0 ，所以 i = 2 是一个有效的分割。

提示：

  • 2 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5

解题思路

这道题目要求我们找到所有有效的分割点，其中在分割点 i 处，前 i+1 个元素的和要大于等于剩余元素的和。

核心思路：前缀和优化

最直观的做法是对每个可能的分割点 i，分别计算左右两部分的和并比较。但这种方法时间复杂度为 O(n²)，对于题目的数据规模可能会超时。

更优的方法是使用前缀和思想。我们可以先计算整个数组的总和，然后遍历每个分割点时维护一个前缀和。对于分割点 i：

  • 左半部分和 = 前缀和
  • 右半部分和 = 总和 - 前缀和

这样我们只需要一次遍历就能解决问题，时间复杂度为 O(n)。

实现细节：

  1. 首先计算数组的总和
  2. 遍历可能的分割点（从 0 到 n-2）
  3. 对于每个分割点 i，累加当前元素到前缀和中
  4. 比较前缀和与剩余和的大小关系
  5. 如果前缀和 >= 剩余和，则计数器加 1

需要注意的是，由于数组元素可能为负数且范围较大，使用 long 类型避免整数溢出。

推荐解法： 前缀和一次遍历，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        int n = nums.size();
        long long total = 0;
        
        // 计算总和
        for (int num : nums) {
            total += num;
        }
        
        long long prefixSum = 0;
        int count = 0;
        
        // 遍历所有可能的分割点（0到n-2）
        for (int i = 0; i < n - 1; i++) {
            prefixSum += nums[i];
            long long rightSum = total - prefixSum;
            
            if (prefixSum >= rightSum) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        total = sum(nums)
        prefix_sum = 0
        count = 0
        
        # 遍历所有可能的分割点（0到n-2）
        for i in range(len(nums) - 1):
            prefix_sum += nums[i]
            right_sum = total - prefix_sum
            
            if prefix_sum >= right_sum:
                count += 1
        
        return count

public class Solution {
    public int WaysToSplitArray(int[] nums) {
        int n = nums.Length;
        long total = 0;
        
        // 计算总和
        foreach (int num in nums) {
            total += num;
        }
        
        long prefixSum = 0;
        int count = 0;
        
        // 遍历所有可能的分割点（0到n-2）
        for (int i = 0; i < n - 1; i++) {
            prefixSum += nums[i];
            long rightSum = total - prefixSum;
            
            if (prefixSum >= rightSum) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var waysToSplitArray = function(nums) {
    const n = nums.length;
    let total = nums.reduce((sum, num) => sum + num, 0);
    
    let prefixSum = 0;
    let count = 0;
    
    // 遍历所有可能的分割点（0到n-2）
    for (let i = 0; i < n - 1; i++) {
        prefixSum += nums[i];
        const rightSum = total - prefixSum;
        
        if (prefixSum >= rightSum) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)
  • 时间复杂度分析： 需要一次遍历计算总和，再一次遍历检查每个分割点，总共 O(n)
  • 空间复杂度分析： 只使用了常量级别的额外空间来存储总和、前缀和和计数器

相关题目