C++ python 用Prefix Sum速解Leetcode 2270 Number of Ways to Split Array

Prefix sum這個概念，只要數學會用Sigma的，問題都不大，基本上就是partial sum。程式要寫的好，老實講該有數學概念真不能少，演算法的東西畢竟是真刀真槍的。

C++ python 用Prefix Sum速解Leetcode 2270  Number of Ways to Split Array

求分割陣列 nums 的方式數量，使得 sum(nums[0...i]) \geq sum(nums[i+1...])。

如何？計算總和sum=sum(nums)

使用loop判斷i是否滿足sum(nums[0..i])\geq sum(nums[i..])=sum-sum(nums[0..i])

「Py3解請進」

-----

Find the number of ways splitting the array nums such that sum(nums[0...i]) \geq sum(nums[i+1...]).

How? compute sum=sum(nums)

Use a loop to find whether i satisfying sum(nums[0..i])\geq sum(nums[i..])=sum-sum(nums[0..i])

[codes on Leetcode]https://leetcode.com/problems/number-of-ways-to-split-array/solutions/6220658/prefix-sum-with-o-1-space-c-beats-100/

[Prefix Sum playlist]https://www.youtube.com/watch?v=1kA_aZHewmU&list=PLYRlUBnWnd5LkYN-5ptHDrtPXOuHm9uSq

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        n=len(nums)
        Sum=sum(nums)
        acc, cnt=0, 0
        for i in range(n-1):
            acc+=nums[i]
            cnt+=(2*acc>=Sum)
        return cnt