長さ K の個別のサブ配列の最大合計-PHPチュートリアル-php.cn

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

Susan Sarandon

リリース： 2024-11-23 19:02:12

オリジナル

454 人が閲覧しました

Maximum Sum of Distinct Subarrays With Length 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 を返します。

制約:

ヒント:

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

解決策:

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

アプローチ：

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

アルゴリズム：

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

ログイン後にコピー

説明：

変数:
- $maxSum: これまでに見つかった有効な部分配列の最大合計を追跡します。
- $currentSum: サイズ k の現在のスライディングウィンドウの合計を保持します。
- $freq: 現在のウィンドウ内の要素の頻度を格納するハッシュテーブル (または連想配列)。
スライディングウィンドウ:
- ループを使用して配列を反復処理します。ウィンドウを移動すると、次のことが行われます。
  - インデックス $i の要素を合計に追加し、その頻度を更新します。
  - ウィンドウサイズが k を超える場合、インデックス $i - k の要素を合計から削除し、その頻度を減らします。
有効なウィンドウチェック:
- ウィンドウサイズが k に達すると (つまり、$i >= k - 1 のとき)、周波数マップ内の個別のキーの数が k に等しいことを確認することで、ウィンドウ内のすべての要素が個別であるかどうかを確認します。該当する場合は、最高額を更新します。
結果を返す:
- 配列を反復処理した後、見つかった最大合計を返します。有効な部分配列が見つからなかった場合、maxSum は 0 のままになります。