1712.-ways-to-split-array-into-three-subarrays.md

1712. Ways to Split Array Into Three Subarrays

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        
        pre_sum = [0]
        for i in range(len(nums)):
            pre_sum.append(pre_sum[-1] + nums[i])
            
        
        ans = 0

        for i in range(1, len(pre_sum) - 2):
            
            f = pre_sum[i]
            
            if f > pre_sum[-1]//3 : break
            target = 2 * f
            left = bisect.bisect_left(pre_sum, target, )
            right = bisect.bisect_right(pre_sum,(f + pre_sum[-1])//2)
            ans += max(0, min(len(nums), right) - max(i+1, left))

            
        return ans % (10**9 + 7)