本文共 2628 字，大约阅读时间需要 8 分钟。

关注我，学习常用算法与数据结构，一题多解，降维打击。

题目描述

[1711]

• https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays/

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

数组被分成三个 非空 连续子数组，从左至右分别命名为 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 <= 10^5

0 <= nums[i] <= 10^4

题目剖析&信息挖掘

此题考查的是对二分算法的应用。题目如果规模较小，也可以用二重枚举来做，复杂度O(n^2)

由于规模较大，所以需要用到二分优化。在求范围和时，要用前缀和优化。

二分查找的特点就是查找的答案具体有单调性， 即某一个解是非可行解，那他的某一边都不是可行解，从而缩小范围。

解题思路

方法一 前缀和+二分查找

分析

/*选定一个i, j进行切割，三个子数组表示如下：left = nums[0,i]mid = nums[i+1, j-1]right = nums[j, len(num)-1]*/func waysToSplit(nums []int) int {
   	sum :=0	for j:=2; j

如上思路，使用二重循环枚举复杂度太高。

考虑优化里面的循环。 以[1, 1, 1, 3, 2, 4, 1]为例. 假设 right = [2, 4, 1], 那么剩下的数组是 [1, 1, 1, 3] 可行的结果有，[1,1,3] ，[1,3] ，[3] 相当是把这个数组再分割一下，使得left<=mid<=right 问题有多少种方法。 由于数组和是固定的，且元素都是整数，所以会随着i的增大left增大，同时mid会减小。 可以得出一个结论，如果left>mid, 那么>=i的位置都是不可行解。对于mid>right也是类似。 所以对于right固定的情况下，对于剩下的数组切割的位置是一个连续的区间。 只要求出这个区间的最左和最右的位置就可以得出答案，可以通过二分查找解决。

思路

func waysToSplit(nums []int) int {
   	InitPre(nums)	sum :=0;	for j:=2; j

注意

• 注意取模
• 剩下数组分割时，要分成2段，每段至少有一个元素。

知识点

• 前缀和
• 二分查找
• 枚举

复杂度

• 时间复杂度：O(nlog(n))
• 空间复杂度：O(n)

参考

代码实现

const MOD = int(1e9)+7var preSum []intfunc InitPre (nums []int) {
   	preSum = make([]int, len(nums))	for i, v := range nums {
   		if i==0 {
   			preSum[i] = v		}else {
   			preSum[i] = preSum[i-1]+v		}	}}func getSum(i, j int) int{
   	if i==0 {
   		return preSum[j];}return preSum[j]-preSum[i-1]}func FindMaxInd(right, lastSum int) int {
   	ind :=-1 // 保存最右边的坐标	l, r := 0, right-1	for l<=r {
   		mid := (l+r)>>1		if getSum(0, mid)<= getSum(mid+1, right)  {
   			if getSum(mid+1, right)<=lastSum {
   // 是可行解				ind = mid//记录最优答案				l=mid+1// 尝试有没有更大的坐标			} else {
   // 说明 getSum(mid+1, right)太大了，<=mid都不是可行解				l=mid+1			}		} else {
   // 不满足，说明>=mid 的分割都不成立			r=mid-1		}	}	return ind}func FindMinInd(right, lastSum int) int {
   	ind :=-1 // 保存最左边的坐标	l, r := 0, right-1	for l<=r {
   		mid := (l+r)>>1		if getSum(0, mid)<= getSum(mid+1, right)  {
   			if getSum(mid+1, right)<=lastSum {
    // 是可行解				ind = mid //记录最优答案				r=mid-1 // 尝试有没有更小的坐标			} else {
    // 说明 getSum(mid+1, right)太大了，<=mid都不是可行解				l=mid+1			}		} else {
    // 不满足，说明>=mid 的分割都不成立			r=mid-1		}	}	return ind}func waysToSplit(nums []int) int {
   	InitPre(nums)	sum :=0;	for j:=2; j

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

转载地址：http://jowrz.baihongyu.com/