[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 を出力します。
私が試したこと:
<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
引用:このコードを使用すると 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){
解決策 2
//インスタグラム@the_eemanulrehmanで私に連絡してください
パブリック クラス 解決策 {
public static int findTriplet(int arr[]int x) {
int sum=0,temp=0,count=0;
for(int i=0;i
[ad_2]
コメント