今日题目

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

思路

根据题意，我们需要计算 $sum(a[0] \space to\space a[i])$ 和 $sum(a[i+1]\space to\space a[n])$。 由于 $sum(a[0]\space to\space a[i + 1]) = sum(a[0]\space to\space a[i]) + a[i+1]$，且 $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])$。 因此，我们可以定义两个变量：$now$ 用于存储 $sum(a[0]\space to\space a[i])$，每次迭代加上 $a[i+1]$；$summ$ 用于存储 $sum(a[0]\space to\space a[n])$。

解题方法

这样，我们只需比较 $now$ 和 $summ - now$ 的大小关系，统计满足条件的下标 i 的数量即可。

复杂度分析

  • 时间复杂度：$O(N)$，N 为序列长度。

  • 空间复杂度：$O(1)$，仅需两个额外变量。

代码

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