2270。配列を分割する方法の数

難易度： medium

トピック： array、prefix sum

0-Indexed integer array nums of length n。

numsには、次の場合は index iで有​​効なsplit が含まれています。

最初のi 1要素の合計は、
• よりも大きい最後のn -i -1要素の合計。
iの右側に少なくとも1つの
• 要素があります。つまり、0
return

。 例1：

入力： nums = [10,4、-8,7]

• output： 2
• 説明： 2つの非空白部品にnumsを分割する3つの方法があります。
インデックス0でnumsを分割します。次に、最初の部分は[10]であり、その合計は10です。2番目の部分は[4、-8,7]であり、その合計は3です。
• インデックス1でnumsを分割します。次に、最初の部分は[10,4]であり、その合計は14です。2番目の部分は[-8,7]、その合計は-1です。 14> = -1以来、i = 1は有効な分割です。 インデックス2でnumsを分割します。次に、最初の部分は[10,4、-8]であり、その合計は6です。2番目の部分は[7]であり、その合計は7です。6したがって、numsの有効な分割の数は2です。
例2：

nums = [2,3,1,0]

2
• 説明：
numsには2つの有効なスプリットがあります。
• index 1でnumsを分割します。次に、最初の部分は[2,3]であり、その合計は5です。2番目の部分は[1,0]であり、その合計は1です。5> = 1であるため、i = 1は有効な分割です。 index 2でnumsを分割します。次に、最初の部分は[2,3,1]であり、その合計は6です。2番目の部分は[0]であり、その合計は0です。
• 制約：
  2 5

-10 5 5

ヒント：
• ^{任意のインデックスIの場合、最初のi要素の合計から最初の（i 1）要素の合計を見つけるにはどうすればよいですか？}
アレイの合計がわかっている場合、最初の（i 1）要素の合計が残りの要素よりも大きいかどうかを確認するにはどうすればよいですか？

解決：

1. 次の手順を使用してアプローチできます：
2. アプローチ：

プレフィックスsum ：最初に、左からの配列の累積合計を計算します。これは、最初のi 1要素の合計をチェックするのに役立ちます。

：アレイの合計を計算します。これは、残りの要素の合計が最初のi 1要素の合計以下であるかどうかを確認するのに役立ちます。

アレイを繰り返します
1. ：有効なインデックスi（0 効率
：合計を繰り返し再計算する代わりに、効率的な比較のためにプレフィックス合計と合計を使用します。
2. このソリューションをphp：
2270に実装しましょう。配列を分割する方法の数
4. 説明：

$ totalsum ：この変数は、numsアレイのすべての要素の合計を保存します。

：これは、インデックスI 1から配列の最後まで残りの要素の合計です。 $ totalsumから$ prefixsumを差し引くことによって計算されます。
1. 有効なスプリットチェック
：各インデックスIについて、プレフィックス合計が残りの合計よりも大きいかどうかを確認します。
2. 時間の複雑さ：
3. o（n）
：アレイを1回ループして、合計を計算し、もう一度有効なスプリットを確認します。したがって、時間の複雑さは、配列の長さに関して線形です。
4. スペースの複雑さ：

：いくつかの追加変数（$ totalsum、$ prefixsum、$ remainingsum）のみを使用しているため、空間の複雑さは一定です。
• 連絡先リンク

このシリーズが役立つと思う場合は、

をgithubでスターにするか、お気に入りのソーシャルネットワークの投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味があります！
• このようなもっと役立つコンテンツが必要な場合は、私にフォローしてください：

linkedin

github