。合計が少なくとも K である最短のサブ配列

862。合計が少なくとも K

である最短の部分配列

難易度: 難しい

トピック: 配列、二分探索、キュー、スライディング ウィンドウ、ヒープ (優先キュー)、プレフィックス合計、モノトニック キュー

整数配列 nums と整数 k を指定すると、合計が少なくとも k である nums の空ではない最短の 部分配列 の長さを返します。そのような サブ配列 がない場合は、-1 を返します。

サブ配列は、配列の連続した部分です。

例 1:

• 入力: nums = [1]、k = 1
• 出力: 1

例 2:

• 入力: nums = [1,2]、k = 4
• 出力: -1

例 3:

• 入力: nums = [2,-1,2]、k = 3
• 出力: 3

制約:

1 5 -10
• 5 ⁵
1 9

解決策:

プレフィックス合計と単調キューを組み合わせたスライディング ウィンドウ アプローチを使用する必要があります。段階的なアプローチは次のとおりです:

手順:

1. プレフィックス合計:

   まず、プレフィックス合計配列を計算します。ここで、インデックス i の各要素は、配列の先頭から i までの要素の合計を表します。接頭辞の合計を使用すると、任意の部分配列の合計を定数時間で計算できます。

2. モノトニックキュー:

   deque (両端キュー) を使用して、prefix_sum 配列のインデックスを維持します。デキューは、プレフィックス合計の昇順で維持されます。
   これは、現在のプレフィックスの合計を以前のプレフィックスの合計と比較することにより、合計が k 以上である部分配列を効率的に見つけるのに役立ちます。

3. スライディング ウィンドウ ロジック:

   • 各インデックス i について、現在のプレフィックス合計と以前のプレフィックス合計 (両端キューに格納されている) の差が k 以上であるかどうかを確認します。
   • その場合、部分配列の長さを計算し、必要に応じて最小長を更新します。

アルゴリズム：

1. prefix_sum 配列をサイズ n 1 で初期化します (n は入力配列の長さです)。ゼロ要素の合計は 0 であるため、最初の要素は 0 です。
2. 両端キューを使用して、prefix_sum 値のインデックスを保存します。デキューは、条件を満たす最短のサブ配列を効率的に見つけるのに役立ちます。
3. 配列内の各要素について、prefix_sum を更新し、両端キューをチェックして、合計が k 以上の最小の部分配列を見つけます。

このソリューションを PHP で実装してみましょう: 862。合計が少なくとも K
である最短の部分配列

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

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

説明：

1. プレフィックス合計配列:

   • prefix_sum 配列内の配列の累積合計を計算します。これは、式 prefix_sum[j 1] - prefix_sum[i].
   を使用して、サブ配列 nums[i...j] の合計を計算するのに役立ちます。

2. モノトニックキュー:

   • 両端キューは、prefix_sum 配列のインデックスを値の昇順に保持します。この順序を維持することで、合計が k 以上である最小の部分配列を効率的に見つけることができます。

3. スライディング ウィンドウ ロジック:

   • prefix_sum 配列をたどるときに、現在の prefix_sum[i] と前の prefix_sum[deque[0]] の差を使用して最小の部分配列を見つけようとします。
   • 差が k 以上の場合、部分配列の長さを計算し、見つかった最小の長さを更新します。

4. 返される結果:

   • 有効な部分配列が見つからない場合は、-1 を返します。それ以外の場合は、サブ配列の最小長を返します。

時間計算量:

• 時間計算量: O(n)、n は入力配列の長さです。各要素は最大 2 回処理されます (両端キューに追加されるときに 1 回、削除されるときに 1 回)。
• 空間の複雑さ: prefix_sum 配列とインデックスの格納に使用される両端キューにより O(n)。

このアプローチにより、入力が大きい場合でもソリューションが効率的に実行されます。

連絡先リンク

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

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

• LinkedIn
• GitHub

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