JavaScriptで数値が2つの平方数の和として表せるか判定する方法

平方数（完全平方数）とは？

数学において、ある自然数が別の自然数とそれ自身との積で表されるとき、その数を平方数（完全平方数）と呼びます。

例えば、9、16、81、289 はすべて平方数です。

• 9 = 3 × 3
• 16 = 4 × 4
• 81 = 9 × 9
• 289 = 17 × 17

問題の定義

自然数 num を引数として受け取るJavaScript関数を作成します。この関数は、次の条件を満たす2つの数 m と n が存在するかどうかを判定する必要があります。

(m * m) + (n * n) = num

そのような数の組み合わせが存在すれば true を、存在しなければ false を返します。

例

入力が以下の場合：

const num = 389;

出力は次のようになります：

const output = true;

これは、389 = (17 × 17) + (10 × 10) と表せるためです。つまり、17² + 10² = 289 + 100 = 389 が成立します。

解法：双方向ポインタ（Two Pointer）を使ったアプローチ

この問題を効率的に解くには、双方向ポインタ（ツーポインター）テクニックが有効です。手順は以下の通りです。

1. 左ポインタ left を 0 に、右ポインタ right を √num の切り捨て値に初期化します。
2. left * left + right * right が num と一致すれば true を返します。
3. 合計が num より小さければ left を増やし、大きければ right を減らします。
4. ポインタが交差するまで繰り返し、見つからなければ false を返します。

この方法では O(√n) の計算量で判定できるため、大きな数でも高速に処理できます。

サンプルコード

const num = 389;

const canSumSquares = (num = 2) => {
  let left = 0, right = Math.floor(Math.sqrt(num));
  while (left <= right) {
    if (left * left + right * right === num) {
      return true;
    } else if (left * left + right * right < num) {
      left++;
    } else {
      right--;
    }
  }
  return false;
};

console.log(canSumSquares(num));

実行結果

コンソールには次のように出力されます：

true

コードのポイント解説

• Math.floor(Math.sqrt(num))：右ポインタの初期値を設定しています。√num を超える整数を二乗しても num より大きくなるため、探索範囲はこれで十分です。
• left <= right：同じ数を2回使うケース（例：50 = 5² + 5²）にも対応できるよう、等号を含めています。
• 計算量：ループは最大 √n 回しか回らないため、時間計算量は O(√n)、空間計算量は O(1) と非常に効率的です。

まとめ

双方向ポインタを使うことで、ある自然数が2つの平方数の和で表せるかどうかを簡潔かつ高速に判定できます。この手法は「Two Sum」系の問題にも応用できる汎用的なテクニックなので、ぜひ覚えておきましょう。