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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

数组被分成三个非空连续子数组，从左至右分别命名为 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>⁵
0 <= nums[i] <= 10⁴

# 思路

双指针

# 解法

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

        int[] sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }

        long result = 0;
        for (int i = 0, j = 1, k = 1; i < nums.length - 2; i++) {
            j = Math.max(j, i + 1);//防止前面一串0,j在原位保持不动
            while (j < nums.length - 1 && sums[i + 1] > sums[j + 1] - sums[i + 1]) {
                j++;
            }
            while (k < nums.length - 1 && sums[k + 1] - sums[i + 1] <= sums[nums.length] - sums[k + 1]) {
                k++;
            }
            if (j > k) {
                break;
            }
            result += k - j;
        }

        return (int) (result % 1000000007);

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 总结

分析出几种情况，然后分别对各个情况实现

#Java