題目

我們稱一個分割整數陣列的方案是 好的 ，當它滿足：

陣列被分成三個 非空 連續子陣列，從左至右分別命名為 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題目，暴力法容易超時，藉助字首和，可以使用雙指標或者二分查詢計算