Medium

题目描述

如果一个整数数组的分割满足以下条件，那么我们称它是 好分割：

  • 数组被分成三个 非空 连续子数组，从左到右分别命名为 left、mid、right。
  • left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个由 非负 整数组成的数组 nums，请返回 好分割 的方案数。由于答案可能会很大，请返回答案对 10^9 + 7 取余 的结果。

示例 1：

输入：nums = [1,1,1]
输出：1
解释：唯一一种好分割的方案是将 nums 分成 [1] [1] [1] 。

示例 2：

输入：nums = [1,2,2,2,5,0]
输出：3
解释：nums 总共有 3 种好分割方案：
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

示例 3：

输入：nums = [3,2,1]
输出：0
解释：nums 没有好分割方案。

提示：

  • 3 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^4

解题思路

这道题要求将数组分成三个非空连续子数组，满足 sum(left) ≤ sum(mid) ≤ sum(right)。

核心思路：

  1. 使用前缀和快速计算子数组和
  2. 固定分割点，利用双指针或二分查找找到有效范围

具体方法： 我们需要确定两个分割点 i 和 j，将数组分成 [0,i]、[i+1,j]、[j+1,n-1] 三部分。

对于固定的第一个分割点 i，我们需要找到所有有效的第二个分割点 j 的范围：

  • j 的最小值：使得 sum(left) ≤ sum(mid)
  • j 的最大值：使得 sum(mid) ≤ sum(right)

优化策略：

  1. 预计算前缀和数组
  2. 对于每个 i，用二分查找快速找到 j 的有效范围
  3. 累加每个 i 对应的有效 j 的个数

时间复杂度分析：

  • 方法一（双指针）：O(n)，因为每个指针最多移动 n 次
  • 方法二（二分查找）：O(n log n)，对每个 i 进行两次二分查找

推荐使用双指针方法，时间复杂度更优且代码简洁。

代码实现

class Solution {
public:
    int waysToSplit(vector<int>& nums) {
        int n = nums.size();
        const int MOD = 1000000007;
        
        // 计算前缀和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        int result = 0;
        int j = 1, k = 1; // j是mid的右边界，k是right的左边界
        
        for (int i = 0; i < n - 2; i++) {
            // left的和
            long long leftSum = prefix[i + 1];
            
            // 找到j的最小值：使得leftSum <= midSum
            while (j <= i || (j < n - 1 && prefix[j + 1] - prefix[i + 1] < leftSum)) {
                j++;
            }
            
            // 找到k的最大值：使得midSum <= rightSum
            while (k < j || (k < n - 1 && prefix[k + 1] - prefix[i + 1] > prefix[n] - prefix[k + 1])) {
                k++;
            }
            
            if (j <= k && k < n - 1) {
                result = (result + k - j + 1) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        n = len(nums)
        MOD = 10**9 + 7
        
        # 计算前缀和
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        result = 0
        j = k = 1  # j是mid的右边界，k是right的左边界
        
        for i in range(n - 2):
            # left的和
            left_sum = prefix[i + 1]
            
            # 找到j的最小值：使得leftSum <= midSum
            while j <= i or (j < n - 1 and prefix[j + 1] - prefix[i + 1] < left_sum):
                j += 1
            
            # 找到k的最大值：使得midSum <= rightSum
            while k < j or (k < n - 1 and prefix[k + 1] - prefix[i + 1] > prefix[n] - prefix[k + 1]):
                k += 1
            
            if j <= k < n - 1:
                result = (result + k - j + 1) % MOD
        
        return result

public class Solution {
    public int WaysToSplit(int[] nums) {
        int n = nums.Length;
        const int MOD = 1000000007;
        
        // 计算前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        int result = 0;
        int j = 1, k = 1; // j是mid的右边界，k是right的左边界
        
        for (int i = 0; i < n - 2; i++) {
            // left的和
            long leftSum = prefix[i + 1];
            
            // 找到j的最小值：使得leftSum <= midSum
            while (j <= i || (j < n - 1 && prefix[j + 1] - prefix[i + 1] < leftSum)) {
                j++;
            }
            
            // 找到k的最大值：使得midSum <= rightSum
            while (k < j || (k < n - 1 && prefix[k + 1] - prefix[i + 1] > prefix[n] - prefix[k + 1])) {
                k++;
            }
            
            if (j <= k && k < n - 1) {
                result = (result + k - j + 1) % MOD;
            }
        }
        
        return result;
    }
}

var waysToSplit = function(nums) {
    const n = nums.length;
    const MOD = 1000000007;
    
    // 计算前缀和
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    let result = 0;
    let j = 1, k = 1; // j是mid的右边界，k是right的左边界
    
    for (let i = 0; i < n - 2; i++) {
        // left的和
        const leftSum = prefix[i + 1];
        
        // 找到j的最小值：使得leftSum <= midSum
        while (j <= i || (j < n - 1 && prefix[j + 1] - prefix[i + 1] < leftSum)) {
            j++;
        }
        
        // 找到k的最大值：使得midSum <= rightSum
        while (k < j || (k < n - 1 && prefix[k + 1] - prefix[i + 1] > prefix[n] - prefix[k + 1])) {
            k++;
        }
        
        if (j <= k && k < n - 1) {
            result = (result + k - j + 1) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型双指针解法二分查找解法
时间复杂度O(n)O(n log n)
空间复杂度O(n)O(n)

说明：

  • 时间复杂度：双指针方法中每个指针最多移动n次，总体为O(n)；二分查找方法对每个位置进行两次二分查找
  • 空间复杂度：主要用于存储前缀和数组，为O(n)

相关题目