JavaScriptで配列内の最長の連続する数列の長さを求める方法

問題の概要

JavaScriptで、整数の配列を引数として受け取る関数を作成します。この関数は、配列内に存在する最長の連続する数列（シーケンス）の長さを見つけて返す必要があります。ここでいう「連続」とは、数値が1ずつ増加して並んでいることを意味し、要素が配列内で隣接しているかどうか（連続配置か非連続配置か）は問いません。

たとえば、入力配列が次の場合を考えてみましょう。

const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1];

このとき出力は 6 になります。最も長い連続する数列が 1, 2, 3, 4, 5, 6 であり、その長さが6だからです。

アプローチ：ハッシュマップによる効率的な解法

この問題は、ハッシュマップ（オブジェクト）を活用することで、ソート不要・線形時間 O(n) で解くことができます。基本的な考え方は以下のとおりです。

• 各数値について、「その数値から始まる連続数列の長さ」をマップに記録します。
• 新しい数値を処理するとき、curr + 1 がすでにマップに存在すれば、その長さに1を足した値を記録します。
• curr - 1 が存在する限り、左方向へ連鎖的に長さを伝播させます。
• すでに処理済みの数値（重複）はスキップします。

コード例

const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1];

const consecutiveSequence = (arr = []) => {
  const consecutiveRight = {};
  let max = 0;

  for (let i = 0; i < arr.length; i += 1) {
    let curr = arr[i];

    // すでに処理済みの数値はスキップ（重複対策）
    if (consecutiveRight[curr] !== undefined) {
      continue;
    }

    // 右隣の数値からの連続長に1を足して記録
    consecutiveRight[curr] = 1 + (consecutiveRight[curr + 1] || 0);

    // 左方向へ連鎖的に長さを更新
    while (consecutiveRight[curr - 1] !== undefined) {
      consecutiveRight[curr - 1] = consecutiveRight[curr] + 1;
      curr -= 1;
    }

    max = Math.max(max, consecutiveRight[curr]);
  }

  return max;
};

console.log(consecutiveSequence(arr));

出力

コンソールには次のように表示されます。

6

別のアプローチ：Set を使ったシンプルな実装

より直感的な方法として、Set を使う実装もあります。各数値について、それが「連続数列の始点」（num - 1 が存在しない場合）であるときだけ右方向へ数え上げることで、無駄な走査を省きます。こちらも平均 O(n) で動作します。

const longestConsecutive = (arr = []) => {
  const numSet = new Set(arr);
  let max = 0;

  for (const num of numSet) {
    // 始点のみカウントを開始
    if (!numSet.has(num - 1)) {
      let curr = num;
      let length = 1;
      while (numSet.has(curr + 1)) {
        curr += 1;
        length += 1;
      }
      max = Math.max(max, length);
    }
  }

  return max;
};

console.log(longestConsecutive([4, 6, 9, 1, 2, 8, 5, 3, -1])); // 6

まとめ

配列をソートせずとも、ハッシュマップやSetを活用すれば、最長連続数列の長さを線形時間 O(n) で求められます。ソートベースの解法（O(n log n)）と比較して大規模なデータでも高速に動作するため、実務面でも有用なテクニックです。負の数や重複を含む配列にも正しく対応できる点もポイントです。