[Java] two pointer O(n) solution (with detailed explanation)
Assume L/M/R are sums of three subarrarys:\n j is the start index of the right subarray\n i1 is the maximum start index of the middle subarray that NOT qualifie
Assume L/M/R are sums of three subarrarys:\n* `j` is the start index of the right subarray\n* `i1` is the maximum start index of the middle subarray that NOT qualifies `M <= R` when `j` is fixed\n* `i2` is the maximum start index of the middle subarray that qualifies `L <= M` when `j` is fixed\n\nWe can fix right subarray each time, and use **binary search** to find `i1` and `i2`. But we also notice that for adjacent `j`s, there is a correlation between their corresponding `i1`s and `i2`s, so we can do it better.\n\nDetailed explanation:\n* pre-calculate prefix sum (can be eliminated to further improve space complexity)\n* move `j` from right to left\n* when `j` moves left one element, `R` will increase and `M` will decrease\n* thus, both `i1` and `i2` has to move to the left side to meet the above requirements\n* so we move `i1` and `i2` to the left until the above requirements are met, then add `i2 - i1` to the res\n\ntime complexity: O(n)\nspace complexity: O(n), can be optimized to O(1) by memorizing `prefix[i1]`, `prefix[i2]`, `prefix[j]`\n\n```\nclass Solution {\n  public int waysToSplit(int[] nums) {\n    final int N = nums.length;\n    int[] prefix = new int[N + 1];\n    for (int i = 0; i < N; i++) {\n      prefix[i + 1] = prefix[i] + nums[i];\n    }\n    long res = 0;\n    int i1 = N - 2;\n    int i2 = N - 2;\n    for (int j = N - 1; j >= 2; j--) {\n      int right = prefix[N] - prefix[j];\n      while (i1 > 0 && prefix[j] - prefix[i1] <= right) {\n\t    // M <= R\n        i1--;\n      }\n      i2 = Math.min(i2, j - 1);\n      while (i2 > 0 && prefix[i2] > prefix[j] - prefix[i2]) {\n\t    // L > M\n        i2--;\n      }\n      if (i2 > i1 && i1 >= 0) {\n        res += (long) (i2 - i1);\n      }      \n    }    \n    return (int) (res % 1_000_000_007);\n  }\n}\n```
[]