【力扣题解】1712. 将数组分成三个子数组的方案数

😊博主目前也在学习，有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈

文章目录

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析
    • 2、代码详解
  • 三、本题知识

一、题目

1、题目描述

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

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

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

2、基础框架

• Java版本框架代码如下：

class Solution {    public int waysToSplit(int[] nums) { }}

3、原题链接

1712. 将数组分成三个子数组的方案数

二、解题报告

1、思路分析

       (1)定义一个数组diff，计算前i个数的和。
       (2)把数组分成三部分需要两个挡板，我们假设先把左边的挡板定住，然后找出右挡板的左边界和右边界，这个边界的长度（假设长度为len）就是分割nums数组的len种情况。遍历nums数组，把每次遍历算出的len相加即为最终结果。
       (3)查找左右边界的方法是二分查找。在查找右边界时，需要满足diff[n] - diff[mid] >= diff[mid] - diff[i]，即right >= mid。在查找左边界时，需要满足diff[mid] - diff[i] >= diff[i]，即mid >= left。

2、代码详解

class Solution {    public int waysToSplit(int[] nums) { int n = nums.length; int[] diff = new int[n + 1]; int res = 0; for(int i = 1;i <= n;i++) {     diff[i] = diff[i - 1] + nums[i - 1]; } for(int i = 1;i < n;i++) {     if(diff[i] * 3 > diff[n]) {  break;     }     //查找右边界     int l1 = i + 1,r1 = n - 1;     while(l1 <= r1) {  int mid = l1 + r1 >> 1;  if(diff[n] - diff[mid] >= diff[mid] - diff[i]) {      l1 = mid + 1;  }else {      r1 = mid - 1;  }     }     //查找左边界     int l2 = i + 1,r2 = n - 1;     while(l2 <= r2) {  int mid = l2 + r2 >> 1;  if(diff[mid] - diff[i] >= diff[i]) {      r2 = mid - 1;  }else {      l2 = mid + 1;  }     }     res = (res + r1 - l2 + 1)%1000000007; } return res%1000000007;    }}

三、本题知识

二分查找+前缀和