1
class Solution {
2
  public int waysToSplit(int[] nums) {
3
    int size = nums.length;
4
    for (int i = 1; i < size; ++i) {
5
      nums[i] += nums[i - 1];
6
    }
7
    int res = 0;
8
    int mod = 1_000_000_007;
9
    for (int i = 0; i < size - 2; ++i) {
10
      int left = searchLeft(nums, i, size - 1);
11
      int right = searchRight(nums, i, size - 1);
12
      if (left == -1 || right == -1) {
13
        continue;
14
      }
15
      res = (res + right - left + 1) % mod;
16
    }
17
    return res;
18
  }
19

20
  private int searchLeft(int[] nums, int left, int right) {
21
    int pos = -1;
22
    int min = nums[left];
23
    int lo = left + 1, hi = right - 1;
24
    while (lo <= hi) {
25
      int mi = lo + (hi - lo) / 2;
26
      int mid = nums[mi] - min;
27
      int max = nums[right] - nums[mi];
28
      if (mid < min) {
29
        lo = mi + 1;
30
      } else if (max < mid) {
31
        hi = mi - 1;
32
      } else {
33
        pos = mi;
34
        hi = mi - 1;
35
      }
36
    }
37
    return pos;
38
  }
39

40
  private int searchRight(int[] nums, int left, int right) {
41
    int pos = -1;
42
    int min = nums[left];
43
    int lo = left + 1, hi = right - 1;
44
    while (lo <= hi) {
45
      int mi = lo + (hi - lo) / 2;
46
      int mid = nums[mi] - min;
47
      int max = nums[right] - nums[mi];
48
      if (mid < min) {
49
        lo = mi + 1;
50
      } else if (max < mid) {
51
        hi = mi - 1;
52
      } else {
53
        pos = mi;
54
        lo = mi + 1;
55
      }
56
    }
57
    return pos;
58
  }
59
}