<!--?php
function
shortestSubarray(
$nums
,
$k
) {
...
...
...
}
$nums1
= [1];
$k1
= 1;
echo
shortestSubarray(
$nums1
,
$k1
) .
"\n"
;
$nums2
= [1, 2];
$k2
= 4;
echo
shortestSubarray(
$nums2
,
$k2
) .
"\n"
;
$nums3
= [2, -1, 2];
$k3
= 3;
echo
shortestSubarray(
$nums3
,
$k3
) .
"\n"
;
?-->
<h3>
説明:
</h3>
<ol>
<li>
<p><strong>プレフィックス合計配列:</strong></p>
<ul>
<li>prefix_sum 配列内の配列の累積合計を計算します。これは、式 prefix_sum[j 1] - prefix_sum[i].</li> を使用して、サブ配列 nums[i...j] の合計を計算するのに役立ちます。
</ul>
</li>
<li>
<p><strong>モノトニックキュー:</strong></p>
<ul>
<li>両端キューは、prefix_sum 配列のインデックスを値の昇順に保持します。この順序を維持することで、合計が k 以上である最小の部分配列を効率的に見つけることができます。</li>
</ul>
</li>
<li>
<p><strong>スライディング ウィンドウ ロジック:</strong></p>
<ul>
<li>prefix_sum 配列をたどるときに、現在の prefix_sum[i] と前の prefix_sum[deque[0]] の差を使用して最小の部分配列を見つけようとします。</li>
<li>差が k 以上の場合、部分配列の長さを計算し、見つかった最小の長さを更新します。</li>
</ul>
</li>
<li>
<p><strong>返される結果:</strong></p>
<ul>
<li>有効な部分配列が見つからない場合は、-1 を返します。それ以外の場合は、サブ配列の最小長を返します。</li>
</ul>
</li>
</ol>
<h3>
時間計算量:
</h3>
<ul>
<li>
<strong>時間計算量:</strong> O(n)、n は入力配列の長さです。各要素は最大 2 回処理されます (両端キューに追加されるときに 1 回、削除されるときに 1 回)。</li>
<li>
<strong>空間の複雑さ:</strong> prefix_sum 配列とインデックスの格納に使用される両端キューにより O(n)。</li>
</ul>
<p>このアプローチにより、入力が大きい場合でもソリューションが効率的に実行されます。</p>
<p><strong>連絡先リンク</strong></p>
<p>このシリーズが役立つと思われた場合は、GitHub で <strong>リポジトリ</strong> にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!</p>
<p>このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:</p>
<ul>
<li><strong>LinkedIn</strong></li>
<li><strong>GitHub</strong></li>
</ul>
<p>以上が。合計が少なくとも K である最短のサブ配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。</p>