[Python3] binary search & 2-pointer
Algo\nCompute prefix array of nums. Any at index i, you want to find index j such at \nprefix[i] <= prefix[j] - prefix[i] <= prefix[-1] - prefix[j]\nThe rest co
**Algo**\nCompute prefix array of `nums`. Any at index `i`, you want to find index `j` such at \n`prefix[i] <= prefix[j] - prefix[i] <= prefix[-1] - prefix[j]`\nThe rest comes out naturally. \n\n**Implementation** \n```\nclass Solution:\n    def waysToSplit(self, nums: List[int]) -> int:\n        prefix = [0]\n        for x in nums: prefix.append(prefix[-1] + x)\n        \n        ans = 0\n        for i in range(1, len(nums)): \n            j = bisect_left(prefix, 2*prefix[i])\n            k = bisect_right(prefix, (prefix[i] + prefix[-1])//2)\n            ans += max(0, min(len(nums), k) - max(i+1, j))\n        return ans % 1_000_000_007\n```\n\n**Analysis**\nTime complexity `O(NlogN)`\nSpace complexity `O(N)`\n\nEdit\nAdding two pointers approach `O(N)` time\n```\nclass Solution:\n    def waysToSplit(self, nums: List[int]) -> int:\n        prefix = [0]\n        for x in nums: prefix.append(prefix[-1] + x)\n        \n        ans = j = k = 0 \n        for i in range(1, len(nums)): \n            j = max(j, i+1)\n            while j < len(nums) and 2*prefix[i] > prefix[j]: j += 1\n            k = max(k, j)\n            while k < len(nums) and 2*prefix[k] <= prefix[i] + prefix[-1]: k += 1\n            ans += k - j \n        return ans % 1_000_000_007\n```
['Python3']