C++ 3 Pointers O(N) Time O(1) Space
Solution 1. Three Pointers\n\nTurn array A into its prefix sum array. \n\nLet i be the last index of the left part. So A[i] is the sum of the left part.\n\nGive
## Solution 1. Three Pointers\n\nTurn array `A` into its prefix sum array. \n\nLet `i` be the last index of the `left` part. So `A[i]` is the sum of the `left` part.\n\nGiven `i`, the last index of the `mid` part is a range. Let it be `[j, k)`.\n\nWhen we increment `i`, `j` and `k` must be monotonically increasing.\n\nTo find `j`, we can increment `j` from `i + 1` until `mid >= left` i.e. `A[j] - A[i] >= A[i]`.\n\nTo find `k`, we can increment `k` from `j` until `mid < right`, i.e. `A[N - 1] - A[k] < A[k] - A[i]`.\n\n```cpp\n// OJ: https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(1)\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& A) {\n        long mod = 1e9+7, ans = 0;\n        for (int i = 1; i < A.size(); ++i) A[i] += A[i - 1];\n        long N = A.size(), i = 0, j = 0, k = 0;\n        for (; i < N; ++i) {\n            long left = A[i];\n            j = max(i + 1, j); // `j` is at least one greater than `i`.\n            while (j < N && A[j] - left < left) ++j; // find the smallest `j` that satisfies `mid >= left`\n            if (j >= N) break; // No room for `k`. Break\n            k = max(k, j);\n            while (k < N - 1 && A.back() - A[k] >= A[k] - A[i]) ++k;\n            ans = (ans + k - j) % mod;\n        }\n        return ans;\n    }\n};\n```
[]