ソートされたサブ配列合計の範囲合計

1508。ソートされたサブ配列合計の範囲合計

中

n 個の正の整数で構成される配列 nums が与えられます。配列から空ではないすべての連続部分配列の合計を計算し、それらを非降順で並べ替えて、n * (n + 1) / 2 の数値の新しい配列を作成しました。

新しい配列内の、左のインデックスから右のインデックスまでの数値の合計 (1 からインデックス付け) を返します。答えは巨大な数になる可能性があるため、10⁹ + 7.

を法として返します。

例 1:

• 入力: nums = [1,2,3,4]、n = 4、left = 1、right = 5
• 出力: 13
• 説明: すべての部分配列の合計は 1、3、6、10、2、5、9、3、7、4 です。それらを非降順で並べ替えると、新しい配列 [1, 2, 3、3、4、5、6、7、9、10]。インデックス le = 1 から ri = 5 までの数値の合計は、1 + 2 + 3 + 3 + 4 = 13 です。

例 2:

• 入力: nums = [1,2,3,4]、n = 4、left = 3、right = 4
• 出力: 6
• 説明: 指定された配列は例 1 と同じです。新しい配列 [1、2、3、3、4、5、6、7、9、10] があります。インデックス le = 3 から ri = 4 までの数値の合計は 3 + 3 = 6 です。

例 3:

• 入力: nums = [1,2,3,4]、n = 4、左 = 1、右 = 10
• 出力: 50

制約:

• n == nums.length
• 1
• 1
• 1

ヒント:

1. すべての合計を計算し、配列に保存します。
2. 次に、左から右のインデックスに移動し、1e9 + 7 を法とする答えを計算します。

解決策:

この問題を解決するには、次の手順に従います:

1. 空ではない連続部分配列の可能なすべての合計を生成します。
2. 結果として得られる合計の配列を並べ替えます。
3. 左のインデックスから右のインデックスまでの要素の合計を計算します (1 から始まります)。
4. 10⁹ + 7 を法とした結果を返します。

このソリューションを PHP で実装してみましょう: 1508。ソートされたサブ配列合計の範囲合計

<?php // Example usage
$nums = array(1, 2, 3, 4);
$n = 4;
$left = 1;
$right = 5;

echo rangeSum($nums, $n, $left, $right); // Output: 13

$left = 3;
$right = 4;
echo rangeSum($nums, $n, $left, $right); // Output: 6

$left = 1;
$right = 10;
echo rangeSum($nums, $n, $left, $right); // Output: 50

?>

説明：

1. 部分配列の合計を生成しています:

   • 部分配列の各開始インデックス i を反復処理します。
   • 開始インデックス i ごとに、インデックス j で終わる部分配列の合計を計算します (j >= i)。
   • 計算された各部分配列の合計を $sums 配列に追加します。

2. 合計の並べ替え:

   • PHP の sort() 関数を使用して、$sums 配列を非降順で並べ替えます。

3. 必要な範囲の合計:

   • 左 1 のインデックスから右 1 のインデックスまで反復します (問題では 1 から始まるインデックスが使用されているため)。
   • オーバーフローを避けるために、モジュロ 10⁹ + 7 を使用するように注意して、この範囲内の要素の合計を累積します。

このソリューションは、すべての部分配列の合計を効率的に生成し、それらを並べ替えて、指定された必要な範囲の合計を計算します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上がソートされたサブ配列合計の範囲合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。