# 1712. Ways to Split Array Into Three Subarrays
###### tags: `Leetcode` `Medium` `Prefix Sum` `Binary Search`
Link: https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/description/
## 思路
### Prefix Sum + Binary Search $O(NlogN)$
用回圈挪动left array的end
然后用binary search找到mid array所有可能的终点(限制条件是mid array的total
sum 大于等于left array的total sum，小于等于mid array+right array的total sum的1/2)
### Prefix Sum + Two Pointers $O(N)$
还是用回圈挪动left array的end
但是仔细观察会发现mid array的end的左端点和右端点都是只会往右边挪的
因此可以用双指针
## Code

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0]
        for x in nums: prefix.append(prefix[-1]+x)
        ans = 0
        mod = 1e9+7
        for i in range(1, n):
            left = bisect.bisect_left(prefix, 2*prefix[i])
            right = bisect.bisect_right(prefix, (prefix[i]+prefix[-1])//2)
            ans += max(0, min(len(nums),right)-max(i+1,left))
        return (int)(ans%mod)

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0]
        for x in nums: prefix.append(prefix[-1]+x)
        ans = 0
        mod = 1e9+7

        left = right = 0
        for i in range(1, n):
            left = max(left, i+1)
            while left<n and prefix[left]<2*prefix[i]: left+=1
            right = max(left, right)
            while right<n and 2*prefix[right]<=prefix[i]+prefix[-1]: right+=1
            ans += right-left
            
        return (int)(ans%mod)