Prefix Sum + Binary Search + Three Pointers Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code 1 [O(NLogN)]\n```\nclass Solution {\npublic:\n    int findMidStart(int left, int n, vector<int> &prefixSum, int target) {\n        int lo = left + 1, hi = n - 2, mid, ans = -1;\n        while (lo <= hi) {\n            mid = lo + (hi - lo) / 2;\n            if (prefixSum[mid] - prefixSum[left] >= target) {\n                ans = mid;\n                hi = mid - 1;\n            } else {\n                lo = mid + 1;\n            }\n        }\n        return ans;\n    }\n    int findMidEnd(int left, int n, vector<int> &prefixSum, int target) {\n        int lo = left + 1, hi = n - 2, mid, ans = -1;\n        while (lo <= hi) {\n            mid = lo + (hi - lo) / 2;\n            if (prefixSum[mid] - prefixSum[left] <= target) {\n                ans = mid;\n                lo = mid + 1;\n            } else {\n                hi = mid - 1;\n            }\n        }\n        return ans;\n    }\n    int waysToSplit(vector<int>& nums) {\n        int n = nums.size(), leftSum, remainingSum, midStart, midEnd, ans = 0, mod = 1e9 + 7;\n        vector<int> prefixSum(n);\n        prefixSum[0] = nums[0];\n        for (int i = 1; i < n; i++) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n        }\n        for (int left = 0; left < n - 2; left++) {\n            leftSum = prefixSum[left];\n            if (leftSum * 3 > prefixSum[n - 1]) {\n                break;\n            }\n            remainingSum = prefixSum[n - 1] - prefixSum[left];\n            midStart = findMidStart(left, n, prefixSum, leftSum);\n            midEnd = findMidEnd(left, n, prefixSum, remainingSum / 2);\n            if (midStart == -1 || midEnd == -1)\n                break;\n            ans = (ans + midEnd - midStart + 1) % mod;\n        }\n        return ans % mod;\n    }\n};\n```\n# Code 2 [O(N)]\n```\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) {\n        int n = nums.size(), ans = 0, mod = 1e9 + 7, left, mid = 0, right = 0;\n        vector<int> prefixSum(n);\n        prefixSum[0] = nums[0];\n        for (int i = 1; i < n; i++) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n        }\n        for (left = 0; left < n - 2; left++) {\n            if (prefixSum[left] * 3 > prefixSum[n - 1])\n                break;\n            mid = max(mid, left + 1);\n            while (mid < n - 1 && prefixSum[mid] < 2 * prefixSum[left]) {\n                mid++;\n            }\n            right = max(mid, right);\n            while (right < n - 1 && (prefixSum[right] - prefixSum[left]) <= (prefixSum[n - 1] - prefixSum[left]) / 2) {\n                right++;\n            }\n            right--;\n            ans = (ans + right - mid + 1) % mod;\n        }\n        return ans;\n    }\n};\n```
['C++']