【C++】有効な三角形の組み合わせ数を二ポインタ法で効率よく求める

非負整数のみから構成される配列が与えられ、その中から3つの要素を選んで三角形の3辺としたときに、実際に三角形を成立させられる組み合わせ(トリプレット)の総数を数えるのがこの問題です。

例えば、入力が [2, 2, 3, 4] の場合、答えは 3 になります。以下の3通りが有効な組み合わせだからです。

• 1番目の「2」を使った [2, 3, 4]
• 2番目の「2」を使った [2, 3, 4]
• [2, 2, 3]

解法の鍵：三角形の成立条件

3辺 a、b、c(c を最長の辺とする)が三角形を成すための条件は、a + b > c が成り立つことです。この性質を利用すると、すべての組み合わせを総当たりで調べる O(n³) の方法よりも、ソート + 二ポインタ(ツーポインタ)法を組み合わせた O(n²) の効率的な解法が実現できます。

アルゴリズムの手順

• ret := 0、n := 配列 nums のサイズとし、nums を昇順にソートします。
• i を n − 1 から 0 まで降順にループし、最も長い辺となる候補 nums[i] を固定します。
  • right := i − 1、left := 0 と初期化します。
  • left < right である間、次の処理を繰り返します。
    • sum := nums[left] + nums[right] を計算します。
    • sum > nums[i] の場合、left から right までのすべての要素は nums[left] 以上であるため、その範囲内の任意のペアが条件を満たします。そこで ret に right − left を一括して加算し、right を 1 減らします。条件を満たさない場合は left を 1 増やして小さい側を調べ直します。
• すべてのループが終わったら ret を返します。

この手法により、固定した最大の辺に対して残りの2辺の候補を線形時間で処理でき、全体の計算量は O(n²)、追加のメモリ使用量は O(1)(ソートに必要な分を除く)に抑えられます。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int triangleNumber(vector<int>& nums) {
      int ret = 0;
      int n = nums.size();
      sort(nums.begin(), nums.end());
      for(int i = n - 1; i >= 0; i--){
         int right = i - 1;
         int left = 0;
         while(left < right){
            int sum = nums[left] + nums[right];
            if(sum > nums[i]){
               ret += right - left;
               right--;
            }else left++;
         }
      }
      return ret;
   }
};
main(){
   vector<int> v = {2,2,3,4};
   Solution ob;
   cout << (ob.triangleNumber(v));
}

入力

[2,2,3,4]

出力

3