長さ K の個別のサブ配列の最大合計

2461。長さ K の個別のサブ配列の最大合計

難易度: 中

トピック: 配列、ハッシュ テーブル、スライディング ウィンドウ

整数配列 nums と整数 k が与えられます。次の条件を満たす num のすべての 部分配列 の最大部分配列合計を見つけます:

• 部分配列の長さは k で、
• 部分配列のすべての要素は 個別です。

条件を満たすすべてのサブ配列の最大サブ配列合計を返します。条件を満たすサブ配列がない場合は、0 を返します。

サブ配列は、配列内の要素の連続した空ではないシーケンスです。

例 1:

• 入力: nums = [1,5,4,2,9,9,9]、k = 3
• 出力: 15
• 説明: 長さ 3 の num の 部分配列 は次のとおりです。
  • [1,5,4] は要件を満たしており、合計は 10 です。
  • [5,4,2] は要件を満たしており、合計は 11 です。
  • [4,2,9] は要件を満たしており、合計は 15 です。
  • [2,9,9] は要素 9 が繰り返されているため要件を満たしません。
  • [9,9,9] は要素 9 が繰り返されているため要件を満たしません。
  • 条件を満たすすべてのサブ配列の最大サブ配列合計であるため、15 を返します

例 2:

• 入力: nums = [4,4,4]、k = 3
• 出力: 0
• 説明: 長さ 3 の num の 部分配列 は次のとおりです。
  • [4,4,4] は要素 4 が繰り返されているため要件を満たしません。
  • 条件を満たす サブ配列がないため、0 を返します。

制約:

• 1 5
• 1 5

ヒント:

1. インデックス i で終わるサイズ k の部分配列からインデックス i 1 で終わるサイズ k の部分配列に移動するときに変更される要素はどれですか?
2. 2 つの要素のみが変更され、i 1 の要素が部分配列に追加され、i - k 1 の要素が部分配列から削除されます。
3. サイズ k の各部分配列を反復処理し、部分配列の合計と各要素の頻度を追跡します。

解決策:

次の手順に従うことができます:

アプローチ：

1. スライディング ウィンドウ: ウィンドウ サイズは k で、現在のウィンドウの合計を維持し、ウィンドウ内のすべての要素が個別であるかどうかを確認しながら、配列内でウィンドウをスライドさせます。
2. ハッシュ テーブル (または連想配列): 連想配列 (ハッシュ テーブル) を使用して、現在のウィンドウ内の要素の頻度を追跡します。いずれかの要素が複数回出現する場合、そのウィンドウは無効になります。
3. ウィンドウの更新: ウィンドウをスライドさせながら、新しい要素 (つまり、ウィンドウに入る要素) を追加し、古い要素 (つまり、ウィンドウから出る要素) を削除します。それに応じて合計を更新し、ウィンドウが有効かどうか (つまり、すべての要素が個別であるかどうか) を確認します。
4. 最大合計を返す: 有効な部分配列間で見つかった最大合計を追跡する必要があります。

アルゴリズム：

1. ハッシュ テーブル freq を初期化して、現在のウィンドウ内の要素の頻度を保存します。
2. サイズ k の最初のウィンドウの合計を計算することから始め、ウィンドウに個別の要素が含まれている場合は結果を保存します。
3. 次の方法でウィンドウを左から右にスライドさせます:
   • ウィンドウから出る要素を左側から削除します。
   • ウィンドウに右から入る要素を追加します。
   • 合計とハッシュ テーブルを更新し、ウィンドウにまだ個別の要素のみが含まれているかどうかを確認します。
4. ウィンドウに有効な個別の要素がある場合は、最大合計を更新します。
5. 有効な部分配列が見つからない場合は、0 を返します。

このソリューションを PHP で実装してみましょう: 2461。長さ K の個別のサブ配列の最大合計

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

// Example usage:
$nums1 = [1,5,4,2,9,9,9];
$k1 = 3;
echo maximumSubarraySum($nums1, $k1); // Output: 15

$nums2 = [4,4,4];
$k2 = 3;
echo maximumSubarraySum($nums2, $k2); // Output: 0
?>

説明：

1. 変数:

   • $maxSum: これまでに見つかった有効な部分配列の最大合計を追跡します。
   • $currentSum: サイズ k の現在のスライディング ウィンドウの合計を保持します。
   • $freq: 現在のウィンドウ内の要素の頻度を格納するハッシュ テーブル (または連想配列)。

2. スライディング ウィンドウ:

   • ループを使用して配列を反復処理します。ウィンドウを移動すると、次のことが行われます。
     • インデックス $i の要素を合計に追加し、その頻度を更新します。
     • ウィンドウ サイズが k を超える場合、インデックス $i - k の要素を合計から削除し、その頻度を減らします。

3. 有効なウィンドウチェック:

   • ウィンドウ サイズが k に達すると (つまり、$i >= k - 1 のとき)、周波数マップ内の個別のキーの数が k に等しいことを確認することで、ウィンドウ内のすべての要素が個別であるかどうかを確認します。該当する場合は、最高額を更新します。

4. 結果を返す:

   • 配列を反復処理した後、見つかった最大合計を返します。有効な部分配列が見つからなかった場合、maxSum は 0 のままになります。

時間計算量:

• O(n)、n は nums 配列の長さです。各要素はスライディング ウィンドウに 1 回追加および削除され、ハッシュ テーブルの操作 (挿入、削除、カウントのチェック) は平均 O(1) です。

空間の複雑さ:

• O(k) は、現在のウィンドウ内の要素の頻度を保存するハッシュ テーブルです。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が長さ K の個別のサブ配列の最大合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。