【解決方法】配列/リスト内のトリプレットの合計数を検索して返します

[ad_1]

ランダムな整数配列/リスト (ARR) と数値 X が与えられました。配列/リスト内の合計が X になるトリプレットを検索して返します。
ノート：
指定された配列/リストには、重複する要素が含まれる場合があります。
入力フォーマット：
最初の行には、実行するテストケースまたはクエリの数を示す整数 ‘t’ が含まれています。次に、テストケースが続きます。

各テストケースまたはクエリの最初の行には、最初の配列/リストのサイズを表す整数 ‘N’ が含まれます。

2 行目には、配列/リスト内の要素を表す ‘N’ 個の単一スペースで区切られた整数が含まれます。

3 行目には整数 ‘X’ が含まれています。
出力フォーマット：
テストケースごとに、配列/リストに存在するトリプレットの総数を出力します。

すべてのテストケースの出力は、別の行に出力されます。
制約 :
1 <= t <= 10^2
0 <= N <= 10^3
0 <= X <= 10^9
サンプル入力 1:

7 サイズ
1 2 3 4 5 6 7
12
サンプル出力 1:
5
サンプル入力 2:

7 サイズ
1 2 3 4 5 6 7
19

サンプル出力 2:
0

入力 2 の説明:
最初のクエリの合計が 19 に等しいトリプレットは存在しないため、0 を出力します。

私が試したこと：

Java

<pre>public static int tripletSum(int[] arr, int num) {
         int count = 0;
        
        for(int i = 0; i<arr.length; i++){
            
             for(int j = i+1; j<arr.length; j++){
                
                 for (int k = j+1; k<arr.length; k++){
                    
                    if ((arr[i] + arr[j] + arr[k])==num){
                        count++;
                    }
                }
            }
        }
        
         return count;
    }
 }

このコードを使用すると O(n^3) 時間の複雑さが得られ、これで制限時間超過エラーが発生します。それを O(n^2) に減らす方法はありますか?

解決策 1
解決策 2

解決策 1

引用：

このコードを使用すると O(n^3) 時間の複雑さが得られ、これで制限時間超過エラーが発生します。それを O(n^2) に減らす方法はありますか?

私のアドバイス：配列を逆に並べ替えてから、並べ替えられた配列を利用してください。

1 5 4 7 2 6 3
sorted in reverse gives
7 6 5 4 3 2 1

すると、配列がソートされているので、検索で早期カットを行うことができます。
ヒント：

For a triplet
if (arr[i]+arr[i+1]+arr[i+2] < num){
    // end of search
}
//Same apply to couple

When you found a triplet
if (arr[x]+arr[y]+arr[z] == num){
next triplet (if there is one) with same x will have nexty >= y and nextz <= z
if (arr[x]+arr[nexty]+arr[nextz] == num){