【ITニュース解説】🧠 Solving LeetCode Until I Become Top 1% — Day `76`

システムエンジニアに求められる重要なスキルの一つに、論理的思考力と問題解決能力がある。これらは、日々のコーディングやシステム設計において直面する様々な課題を効率的に解決するために不可欠である。世界中のエンジニアが自身のスキルを磨くために利用しているのが、LeetCodeのようなオンラインのプログラミング問題演習サイトだ。ここでは、ある一つのプログラミング問題とそのエレガントな解法について解説する。

今回取り上げる問題は、「与えられた整数nに対して、合計すると0になるn個の互いに異なる（ユニークな）整数からなる配列を作成せよ」というものである。例えば、nが5であれば、[-2, -1, 0, 1, 2]という配列が答えの一例となる。これらの整数はすべて異なっており、合計は0になる。もしnが4であれば、[-2, -1, 1, 2]などが考えられる。この問題のポイントは、「合計が0」と「n個のユニークな整数」という二つの条件を同時に満たす配列をいかにして効率的に見つけ出すかにある。

この種の問題に初めて直面したとき、多くの人がまず試行錯誤的なアプローチを考えるかもしれない。例えば、ランダムにn個の整数を生成し、その合計が0になるまで調整を繰り返すといった方法だ。これはブルートフォース（力任せ）な考え方であり、運が良ければ答えが見つかるかもしれないが、非常に非効率的で、nが大きくなると現実的な時間内に答えを導き出すことは困難になる。優れたエンジニアは、このような行き当たりばったりの方法ではなく、問題の構造を見抜き、より体系的で確実な解決策、すなわちアルゴリズムを考案する。

この問題の核心を突くスマートな解決策は、数学的な性質、特に「対称性」を利用することにある。任意の整数とその符号を反転させた数のペア、例えば「+1と-1」や「+5と-5」を考えると、その合計は必ず0になる。この単純な事実が、問題解決の強力な鍵となる。この「正の数と負の数のペア」というアイデアを利用すれば、答えを直接的に、かつ効率的に構築していくことができる。

具体的な手順は次のようになる。まず、作りたい配列の要素数nが偶数か奇数かで場合分けして考える。もしnが偶数、例えばn=4の場合を考えてみよう。この場合、2つのペアを作れば合計4つの要素が得られる。例えば、「+1と-1」のペアと、「+2と-2」のペアを用意する。これらを組み合わせた配列[-2, -1, 1, 2]は、4つのユニークな整数で構成され、合計は(-2 + 2) + (-1 + 1) = 0となり、問題の条件を完全に満たす。

次に、nが奇数、例えばn=5の場合を考える。この場合は、まずn-1、つまり4つの要素を偶数の時と同じ方法で作成する。先ほどの例で言えば、[-2, -1, 1, 2]という配列だ。この時点で要素は4つあり、合計は0である。残るはあと1つのユニークな要素を追加するだけだが、合計を0のまま維持しなければならない。ここで活躍するのが「0」という数字である。0は、どんな数に加えてもその値を変えない。したがって、作成した配列に0を追加すれば、要素数は5になり、合計も0のまま保たれる。結果として得られる[-2, -1, 1, 2, 0]は、5つのユニークな整数からなり、合計が0という条件を満たす完璧な答えとなる。

このアルゴリズムをプログラムとして実装するのは非常にシンプルだ。まず、結果を格納するための空の配列を用意する。次に、1からnを2で割った商（小数点以下切り捨て）までの整数についてループ処理を行う。ループの中で、現在の整数とその整数にマイナスを付けたものの両方を配列に追加していく。例えばn=5の場合、5を2で割った商は2なので、ループは1と2について実行される。まず1と-1が配列に追加され、次に2と-2が追加される。ループが終了した時点で、配列には[1, -1, 2, -2]が格納されている。最後に、nが奇数であるかどうかを判定し、もし奇数であれば配列に0を追加する。これでアルゴリズムは完成だ。

この解法の効率性を評価する指標として、計算量という概念がある。時間計算量は、プログラムの実行時間が入力サイズnに対してどれだけ増加するかを示し、空間計算量は、使用するメモリ量がnに対してどれだけ増加するかを示す。このアルゴリズムでは、n個の要素を生成するためにnに比例した回数の操作を行うため、時間計算量はO(n)と表現される。また、n個の要素を格納する配列が必要なため、空間計算量もO(n)となる。これは、ブルートフォースのような非効率な方法とは比較にならないほど高速かつ省メモリな、非常に優れた解法であると言える。

この問題から学べることは、単に一つのパズルを解くテクニックにとどまらない。それは、複雑に見える問題でも、その本質的な構造や数学的な性質を見抜くことで、シンプルかつエレガントな解決策を導き出せるということだ。力任せに試行錯誤するのではなく、対称性などの規則性を利用して答えを直接構築していくというアプローチは、より大規模で複雑なシステムの設計やデータ処理においても応用できる、エンジニアにとって普遍的で価値のある思考法なのである。