[Java] Prefix Sum -- O(n) time
the key point here is how can you find the right boundary between second and third array.\nOne way is to use binary search by target value; (O(nlgn))\nThe other
the key point here is how can you find the right boundary between second and third array.\nOne way is to use binary search by target value; (O(nlgn))\nThe other way is use another pointer to find the cutting point, naively from i+1 to n - 2 everytime when i increases (O(n2)). However, this can be further optimized by not starting from i+1 everytime but use the previously scanned value. (O(n))\n\n```\nclass Solution {\n    public int waysToSplit(int[] nums) {\n        int mod = (int) Math.pow(10, 9) + 7;\n        int n = nums.length;\n        int[] sums = new int[n+1];\n        for (int i = 1; i <= n; i++) {\n            sums[i] = sums[i-1] + nums[i-1];\n        }\n        \n        long res = 0;\n        int j = 1;\n        int k = 2;\n        for (int i = 0; i < n - 2; i++) {\n            int left = sums[i+1];\n            int target = (sums[n] - sums[i+1]) / 2;\n            if (target < left) {\n                break;\n            }\n            \n            while (j <= i || j < n - 1 && sums[j+1] - sums[i+1] < left) {\n                j++;\n            }\n            \n            while (k < j || k < n - 1 && sums[k+1] - sums[i+1] <= sums[n] - sums[k+1]) {\n                k++;\n            }\n            res = (res + k - j) % mod;\n        }\n        return (int) res;\n    }\n}\n```
[]