Today’s problem

https://leetcode.com/problems/number-of-ways-to-split-array/description/

Intuition

We need to calculate $sum(a[0] \space to\space a[i])$ and $sum(a[i+1]\space to\space a[n])$ according to the question. Since $sum(a[0]\space to\space a[i + 1]) = sum(a[0]\space to\space a[i]) + a[i+1]$ and $sum(a[i+1]\space to\space a[n]) = sum(a[0]\space to\space a[n]) - sum(a[0]\space to\space a[i])$. Therefore, we can new two variables. One $now$ that stores $sum(a[0]\space to\space a[i])$ and add $a[i+1]$ to it every iteration, one $summ$ that stores $sum(a[0]\space to\space a[n])$.

Approach

In this case, we only need to compare $now$ and $summ - now$. Then count all i that apply.

Complexity

  • Time complexity: $O(N)$, N is the length of the sequence.

  • Space complexity: $O(1)$, two new varables are stored.

Code

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        now,summ, ans = 0, 0, sum(nums)
        for num in nums[:-1]:
            now += num
            if now >= summ - now:
                ans += 1
            
        return ans

image.png