【ITニュース解説】Blind 75 | Arrays & Hashing — 10 3Sum

システムエンジニアを目指す上で、アルゴリズムとデータ構造の理解は非常に重要だ。それは、与えられた問題を効率的に解決するための思考力と実践力を養う基本だからだ。今回解説する記事は、「Blind 75」というプログラミング問題集の中の一つ、「3Sum」という問題を扱っている。Blind 75は、IT企業の面接対策として広く利用されており、実践的なアルゴリズムのスキルを試すのに最適な問題が集められている。その中でも「配列」という基本的なデータ構造と、「ハッシュ」や「Two Pointers」といったテクニックを組み合わせて解くこの「3Sum」問題は、初心者が学ぶべきポイントが豊富に詰まっている。

「3Sum」問題は、具体的にどのような内容なのだろうか。この問題は、与えられた整数の配列の中から、合計がゼロになるような異なる三つの要素の組み合わせをすべて見つけ出すことを求める。例えば、[-1, 0, 1, 2, -1, -4]という配列が与えられた場合、合計がゼロになる三つの組み合わせは [-1, 0, 1] や [-1, -1, 2] などとなる。単純に聞こえるかもしれないが、効率的に、そして重複なくすべての組み合わせを見つけることがこの問題の肝となる。

この問題を初めて解く際に多くの人が思いつくのが、三つの要素をすべて順番に試していく方法だろう。配列の中から一つ目の要素を選び、次に二つ目の要素を選び、最後に三つ目の要素を選ぶ、というように、すべての可能な三つの組み合わせを生成し、それぞれが合計ゼロになるかを確認する方法だ。これは「力任せ（Brute Force）」なアプローチと呼ばれる。しかし、この方法は配列の要素数が n 個だとすると、おおよそ n × n × n 回の計算が必要になる。専門用語では「計算量O(n^3)」と表現され、配列の要素数が少し増えるだけで処理時間が爆発的に増大し、実用的な速度では動作しなくなってしまう。例えば、要素数が1000個の配列であれば、10億回もの計算が必要になる計算だ。これでは現実のシステムでは使い物にならない。

そこで、もっと効率的な解決策が求められる。この記事で紹介されている、より洗練されたアプローチは、主に「ソート（Sorting）」と「Two Pointers（二つのポインタ）」というテクニックを組み合わせるものだ。

まず、最初の重要なステップは、与えられた配列を昇順にソートすることだ。ソートとは、配列の要素を小さい順や大きい順に並べ替える処理のことだ。ソートすることで、配列内の値の大小関係が明確になり、隣接する要素が同じ値であることがすぐにわかるようになる。これは後の処理で重複を効率的に排除するために非常に役立つ。ソート自体の計算量は、通常「O(n log n)」であり、O(n^3)に比べてはるかに効率的だ。

配列をソートしたら、次に「Two Pointers」テクニックを適用する。まず、ソートされた配列の中から、一番左の要素から一つずつ「基準となる要素（仮に a とする）」を選んでいく。この a を選んだら、残りの配列（a の右側の部分）に対して、「合計が 0 - a（つまり、a と合わせたときにゼロになる二つの数）となるような二つの要素（仮に b と c とする）を見つける」という問題に変換される。これは「2Sum」問題と呼ばれ、「3Sum」問題の内部で登場する、より簡単な問題だ。

この2Sum問題を解くためにTwo Pointersが活躍する。a の右側の配列の先頭に「左ポインタ（left）」を置き、同じ配列の末尾に「右ポインタ（right）」を置く。そして、left が指す要素 b と right が指す要素 c を選び、a + b + c の合計を計算する。

• もし合計がゼロになれば、目標の三つの組み合わせ (a, b, c) が見つかったことになる。この組み合わせを結果として保存し、次の組み合わせを探すために left ポインタを右に一つ進め、right ポインタを左に一つ進める。
• もし合計がゼロより小さい場合（つまり、マイナスの値が大きい、あるいはプラスの値が小さい）、合計を大きくする必要がある。そのため、left ポインタを右に一つ進めることで、より大きな b の値を選び、合計を増やすことを試みる。
• もし合計がゼロより大きい場合（つまり、プラスの値が大きい、あるいはマイナスの値が小さい）、合計を小さくする必要がある。そのため、right ポインタを左に一つ進めることで、より小さな c の値を選び、合計を減らすことを試みる。 この left と right のポインタを動かす操作を、left ポインタが right ポインタを追い越すまで繰り返す。

この際、非常に重要なのが「重複の排除」だ。例えば、配列が [-1, -1, 0, 1, 2] のように同じ値を含む場合、単にポインタを動かすだけだと [-1, 0, 1] という組み合わせを二回見つけてしまう可能性がある。これを防ぐために、基準となる要素 a を選ぶ際、もし前の a と同じ値であればそのループはスキップする。同様に、b と c を見つけた後、left や right ポインタを移動させる際も、次の要素が現在の要素と同じ値であればさらにポインタを動かし、重複を避ける。この重複排除の処理を適切に行うことで、結果セットに同じ組み合わせが複数含まれることを防ぎ、正しく「異なる三つの要素の組み合わせ」を得ることができる。

このソートとTwo Pointersを組み合わせたアプローチでは、ソートにO(n log n)、その後のTwo Pointersを使った探索部分がO(n^2)となるため、全体としての計算量はO(n^2)に大幅に改善される。これは最初の力任せなO(n^3)に比べて格段に高速で、要素数が1000個でも100万回程度の計算で済むことになる。

記事のタイトルには「Arrays & Hashing」とあるが、この「3Sum」問題の一般的な最適解法はソートとTwo Pointersであり、ハッシュテーブル（ハッシュマップ）は2Sum問題などでは強力だが、3SumではソートとTwo Pointersの組み合わせがより効率的で直感的になることが多い。

この「3Sum」問題を通じて、システムエンジニアを目指す初心者は、単に問題を解決するだけでなく、いかに効率的に解決するかという「アルゴリズム思考」の基礎を学ぶことができる。データ構造（配列）とアルゴリズム（ソート、Two Pointers）を適切に組み合わせることで、目覚ましいパフォーマンスの改善が実現できることを実感できる良い例だ。これらの知識は、より複雑なシステム設計や問題解決に取り組む上で不可欠な土台となるだろう。