【ITニュース解説】LeetCode Series: SlidingWindow (3/5)

プログラミングの問題を解く際、効率的なアプローチを知っていると、解決までの道のりがぐっと短くなることがある。その中でも「スライディングウィンドウ」というテクニックは、特に配列や文字列の連続する要素を扱う問題で非常に強力な味方となる。システムエンジニアを目指す上で、このようなアルゴリズムの基礎を理解することは不可欠である。

スライディングウィンドウは、文字通り「窓」のような範囲を配列や文字列の上で滑らせながら処理を進める手法である。このテクニックは、問題文に「部分文字列（substring）」「部分配列（subarray）」「ブロック（block）」といった連続した要素を指す言葉が登場したとき、あるいは「最長（longest）」「最大（maximum）」「最小（minimum）」といった条件が付随し、さらに「サイズkの（of size k）」といった特定の範囲に関する指定がある場合に、その有効性を示すことが多い。

基本的な考え方は、配列や文字列の一部に注目し、その注目する範囲、つまり「ウィンドウ」を二つのポインタ、通常は左端と右端を示すポインタで管理することにある。このウィンドウは、問題の要件に応じて拡大したり縮小したりしながら、配列全体を端から端まで移動していく。重要なのは、ウィンドウ内の要素にのみ関心を持ち、それ以外の配列の要素は一旦考慮しないという点だ。これにより、配列全体を何度も繰り返し走査するような非効率な処理を避け、計算量を大幅に削減できる場合が多い。

スライディングウィンドウには大きく分けて二つのタイプが存在する。一つは「固定サイズウィンドウ」である。これは、ウィンドウの大きさが常に一定で、左右のポインタを同時に動かすことでウィンドウ全体を配列に沿ってスライドさせていくタイプだ。例えば「長さkの部分配列における最大値を求める」といった問題で使われる。もう一つは「動的ウィンドウ」で、こちらはウィンドウの大きさが問題の条件によって柔軟に変化する。例えば「合計値が特定の条件を満たす最小の部分配列を求める」といった場合、ウィンドウを拡大したり縮小したりして、条件を満たす最適なサイズを見つけることになる。

スライディングウィンドウを適用する際の一般的な手順を見てみよう。まず、二つのポインタ、leftPtr と rightPtr を両方とも配列の先頭、つまりインデックス 0 で初期化する。次に、rightPtr を配列の末尾に到達するまで一つずつ進めていき、ウィンドウを拡大していく。この拡大の過程で、問題の条件が満たされたり、特定の閾値を超えたりした場合、今度は leftPtr を進めてウィンドウを縮小する必要があるかもしれない。これらのポインタの動きを通じて、現在のウィンドウ内の要素に対して、合計値を計算したり、最大値や最小値を更新したりといった必要な処理を行う。この繰り返しによって、配列全体を効率的に調べ上げることが可能になる。

具体的な問題を通して、このテクニックがどのように活用されるかを理解しよう。LeetCodeの「643. Maximum Average Subarray I（最大平均部分配列I）」という問題がある。これは「整数配列 nums と整数 k が与えられたとき、長さ k の連続する部分配列の中で、平均値が最大となるものを探し、その最大平均値を返す」という内容だ。

この問題文から、「部分配列」「長さ k」というキーワードが見えるため、スライディングウィンドウ、特にウィンドウサイズが k で固定される「固定サイズウィンドウ」を使うのが最適だと判断できる。平均値を最大にするためには、合計値を最大にすれば良い。なぜなら、平均値を計算する際に割る数 k は固定だからだ。

具体的なアプローチは以下のようになる。まず、最初の長さ k の部分配列の合計値を計算する。これを、現時点での最大合計値 max_sum として記録する。例えば、nums = [1, 12, -5, -6, 50, 3], k = 4 という配列と k が与えられたとする。最初のウィンドウは [1, 12, -5, -6] であり、その合計値は 1 + 12 - 5 - 6 = 2 となる。これが最初の max_sum である。

次に、このウィンドウを右に一つずつスライドさせていく。ウィンドウをスライドさせる際には、左端の要素をウィンドウから「削除」し、右端に新しい要素を一つ「追加」することで、合計値を効率的に更新できる。例えば、先ほどの例でウィンドウが [1, 12, -5, -6] から [12, -5, -6, 50] にスライドする場合、合計値は max_sum から 1 を引き、新しく加わった 50 を足すことで更新できる。つまり、2 - 1 + 50 = 51 となる。この新しい合計値 51 を、現在の max_sum (2) と比較し、もし 51 の方が大きければ max_sum を 51 に更新する。この処理を rightPtr が配列の末尾に到達するまで繰り返すのだ。

最終的に、すべての可能な長さ k の部分配列を一度ずつ調べ終えたとき、max_sum には配列 nums の中で長さ k の部分配列の最大合計値が格納されている。この max_sum を k で割ることで、最大平均値が得られる。この問題では、平均値を浮動小数点数（double型）で返すよう求められているため、計算結果を適切な型で返すことを忘れないようにする。

このスライディングウィンドウのアプローチは、配列の各要素を一度だけ処理するため、時間計算量は配列の長さに比例する O(n) となる。もし、すべての長さ k の部分配列を個別に計算するブルートフォース（力任せ）な方法を取ると、O(n^2) の計算量が必要になる場合が多いが、スライディングウィンドウを使うことで、はるかに高速に問題を解決できる。また、追加のデータ構造をほとんど必要としないため、空間計算量も O(1) と非常に効率的である。

まとめると、スライディングウィンドウは、連続する要素を扱う問題において、二つのポインタを使って効率的に部分的な範囲（ウィンドウ）を管理する強力なテクニックである。問題文中の「最長」「最大」「最小」「部分文字列」「部分配列」「サイズk」といったキーワードは、このテクニックを使うべきヒントとなることが多い。ウィンドウには、サイズが固定のものと、条件によってサイズが変わる動的なものの二種類がある。基本的なアプローチは、左右のポインタを初期化し、右ポインタを動かしてウィンドウを拡大し、必要に応じて左ポインタを動かしてウィンドウを縮小しながら、ウィンドウ内の要素に対して処理を行うという流れになる。これらのポイントを理解し活用することで、複雑な問題をシンプルかつ効率的に解決する能力が身につくだろう。