JavaScriptで配列から三角形を作れる組み合わせの数を数える方法

問題

数値の配列 arr を第一引数(唯一の引数)として受け取る JavaScript 関数を作成します。

この関数の目的は、配列から選んだ3つの数値を三角形の3辺としたときに、実際に三角形が成立する組み合わせ(三つ組)の総数を数えることです。

たとえば、関数への入力が次のようだった場合:

const arr = [2, 2, 3, 4];

期待される出力は次のとおりです。

const output = 3;

出力の解説

有効な組み合わせは以下の3通りです。

2,3,4(1つ目の2を使用)
2,3,4(2つ目の2を使用)
2,2,3

三角形の成立条件

3つの辺 a、b、c(a ≤ b ≤ c)が三角形を構成するためには、最も長い辺が他の2辺の合計より短くなければなりません。つまり「a + b > c」という不等式を満たす必要があります。この性質を利用することで、効率的に判定を行えます。

サンプルコード

以下がその実装例です。

const arr = [2, 2, 3, 4];
const countTriangle = (arr = []) => {
   arr.sort((a, b) => a - b)
   let k = 2
   let count = 0
   for (let i = 0; i < arr.length - 2; i++) {
      for (let j = i + 1; j < arr.length - 1; j++) {
         k = j + 1
         while (arr[k] < arr[i] + arr[j]) {
            k += 1
         }
         count += k - j - 1
      }
   }
   return count
};
console.log(countTriangle(arr));

コードの解説

まず配列を昇順にソートし、最小の2辺 i と j を固定します。続いて内側の while ループで、arr[i] + arr[j] より小さい要素の範囲を求めます。ソート済みであるため、この範囲に含まれるすべての要素は第3辺として三角形を成立させられます。k - j - 1 がその組み合わせの数に相当し、これを累積していく仕組みです。全探索(O(n³))に比べ、この方法では処理量を大幅に抑えられます。

出力結果

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

3