题目

我们称一个分割整数数组的方案是 好的 ，当它满足：

数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。

left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。

由于答案可能会很大，请你将结果对 109 + 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

解释：没有好的分割方案。

提示：3 <= nums.length <= 105

0 <= nums[i] <= 104

解题思路分析

1、前缀和+双指针；时间复杂度O(n)，空间复杂度O(n)

func waysToSplit(nums []int) int {	res := 0	n := len(nums)	arr := make([]int, n+1)	for i := 0; i < n; i++ {		arr[i+1] = arr[i] + nums[i]	}	left, right := 2, 2	for i := 1; i <= n-1; i++ {		first := arr[i] // 第1个数		left = max(left, i+1)		right = max(right, i+1)		for left <= n-1 && arr[left]-first < first { // 找到第一个满足的中间数组左边坐标			left++		}		for right <= n-1 && arr[right]-first <= arr[n]-arr[right] {			right++		}		if left <= right {			res = (res + right - left) % 1000000007		}	}	return res % 1000000007}func max(a, b int) int {	if a > b {		return a	}	return b}

2、前缀和+二分查找；时间复杂度O(nlog(n))，空间复杂度O(n)

func waysToSplit(nums []int) int {	res := 0	n := len(nums)	arr := make([]int, n+1)	for i := 0; i < n; i++ {		arr[i+1] = arr[i] + nums[i]	}	for i := 1; i <= n-1; i++ {		first := arr[i] // 第1个数		if first*3 > arr[n] {			break		}		left, right := i+1, n-1		for left <= right {			mid := left + (right-left)/2			if arr[n]-arr[mid] < arr[mid]-first {				right = mid - 1			} else {				left = mid + 1			}		}		b := left		left, right = i+1, n-1		for left <= right {			mid := left + (right-left)/2			if arr[mid]-first < first {				left = mid + 1			} else {				right = mid - 1			}		}		a := left		res = (res + b - a) % 1000000007	}	return res % 1000000007}

Medium题目，暴力法容易超时，借助前缀和，可以使用双指针或者二分查找计算