配列を分割する方法の数

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

難易度: 中

トピック: 配列、プレフィックス合計

長さ n の 0 インデックス付き 整数配列 nums が与えられます。

以下に該当する場合、

nums にはインデックス i に 有効な分割が含まれています:

• 最初の i 1 要素の合計は、最後の n - i - 1 要素の合計以上です。
• i の右側には 少なくとも 1 つの 要素があります。つまり、0

有効な分割の数を nums で返します。

例 1:

• 入力: 数値 = [10,4,-8,7]
• 出力: 2
• 説明: num を 2 つの空でない部分に分割するには 3 つの方法があります。
  • インデックス 0 で数値を分割します。最初の部分は [10] で、その合計は 10 です。2 番目の部分は [4,-8,7] で、その合計は 3 です。10 >= 3 なので、 、i = 0 は有効な分割です。
  • インデックス 1 で数値を分割します。最初の部分は [10,4] で、その合計は 14 です。2 番目の部分は [-8,7] で、その合計は -1 です。 14 >= -1 であるため、i = 1 は有効な分割です。
  • インデックス 2 で数値を分割します。次に、最初の部分は [10,4,-8] で、その合計は 6 です。2 番目の部分は [7] で、その合計は 7 です。 7、i = 2 は有効な分割ではありません。
  • したがって、nums での有効な分割数は 2 です。

例 2:

• 入力: 数値 = [2,3,1,0]
• 出力: 2
• 説明: nums には 2 つの有効な分割があります。
  • インデックス 1 で数値を分割します。最初の部分は [2,3] で、その合計は 5 です。2 番目の部分は [1,0] で、その合計は 1 です。5 >= 1 であるため、 i = 1 は有効な分割です。
  • インデックス 2 で数値を分割します。最初の部分は [2,3,1] で、その合計は 6 です。2 番目の部分は [0] で、その合計は 0 です。6 >= 0 であるため、 i = 2 は有効な分割です。

制約:

• 2 5
• -10⁵ 5

ヒント:

1. 任意のインデックス i について、最初の i 要素の合計から最初 (i 1) の要素の合計を見つけるにはどうすればよいですか?
2. 配列の合計がわかっている場合、最初の (i 1) 要素の合計が残りの要素以上であるかどうかをどのように確認できますか?

解決策:

次の手順を使用してこれにアプローチできます:

アプローチ：

1. Prefix Sum: まず、配列の累積合計を左から計算します。これは、最初の i 1 要素の合計をチェックするのに役立ちます。
2. Total Sum: 配列の合計を計算します。これは、残りの要素の合計が最初の i 1 要素の合計以下であるかどうかを確認するのに役立ちます。
3. 配列を反復処理します: 有効なインデックス i (0
4. 効率: 合計を繰り返し再計算する代わりに、プレフィックス合計と合計合計を使用して効率的に比較します。

このソリューションを PHP で実装してみましょう: 2270。配列を分割する方法の数

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function waysToSplitArray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [10, 4, -8, 7];
echo waysToSplitArray($nums1); // Output: 2

$nums2 = [2, 3, 1, 0];
echo waysToSplitArray($nums2); // Output: 2
?>

説明：

1. $totalSum: この変数は、nums 配列内のすべての要素の合計を格納します。
2. $prefixSum: この変数は、左から (インデックス i まで) の要素の累積合計を追跡します。
3. $remainingSum: これは、インデックス i 1 から配列の最後までの残りの要素の合計です。 $totalSum から $prefixSum を減算して計算されます。
4. 有効な分割チェック: 各インデックス i について、プレフィックスの合計が残りの合計以上であるかどうかをチェックします。

時間計算量:

• O(n): 配列を 1 回ループして合計を計算し、もう一度ループして有効な分割を確認します。したがって、時間計算量は配列の長さに対して線形です。

空間の複雑さ:

• O(1): いくつかの追加変数 ($totalSum、$prefixSum、$remainingSum) のみを使用しているため、空間の複雑さは一定です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が配列を分割する方法の数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。