C++で配列内の合計がゼロになるすべてのトリプレットを見つける方法

はじめに

このチュートリアルでは、配列の中から合計がゼロになる3つの要素(トリプレット)をすべて見つけるC++プログラムを作成します。

まずは、問題を解決するための手順を確認しましょう。

• ダミーデータを含む配列を作成します。

• 3つの要素を選ぶために、三重のネストしたループを記述し、配列の末尾まで反復処理を行います。

  • 選んだ3つの要素を加算します。

  • その合計が0と等しいかどうかを比較します。

  • 等しい場合は、該当する3つの要素を出力します。

コード例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
void findTripletsWithSumZero(int arr[], int n){
   bool is_found = false;
   for (int i = 0; i < n-2; i++) {
      for (int j = i+1; j < n-1; j++) {
         for (int k = j+1; k < n; k++) {
            if (arr[i]+arr[j]+arr[k] == 0) {
               cout << arr[i] << " " << arr[j] << " " << arr[k] << endl;
               is_found = true;
            }
         }
      }
   }
   if (is_found == false) {
      cout << "Triplets doesn't exist"<<endl;
   }
}
int main() {
   int arr[] = {0, 1, -1, 2, 2, -4, 3, 4};
   findTripletsWithSumZero(arr, 8);
   return 0;
}

出力結果

上記のプログラムを実行すると、次のような結果が得られます。

0 1 -1
0 -4 4
1 -4 3
2 2 -4

計算量について

このアプローチは3つのネストしたループを使用するため、時間計算量はO(n³)となります。配列のサイズが大きくなると処理に時間がかかる点に注意してください。より効率化したい場合は、配列をあらかじめソートしておき、2ポインタ法を組み合わせることで、時間計算量をO(n²)まで抑えることが可能です。

まとめ

本チュートリアルでは、三重ループを用いて配列内の合計がゼロになるトリプレットをすべて検出する方法を学びました。内容について質問がある場合は、ぜひコメント欄でお知らせください。