合計がゼロのすべてのトリプレットを検索


難易度 ミディアム
よく聞かれる Amazon (アマゾン) GEヘルスケア Google ハイキング
配列 ハッシュ 検索 並べ替え(ソート)

「合計がゼロのすべてのトリプレットを検索する」という問題は、正と負の両方の数を含む配列が与えられていることを示しています。 問題ステートメントは、合計が0に等しいトリプレットを見つけるように要求します。

合計がゼロのすべてのトリプレットを検索

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

説明

これらは、合計が0であるトリプレットです。

(-2 + -1 + 3 = 0)(-2 + 0 + 2 = 0)(-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

説明

これらは、数の合計が0⇒-5+ 2 + 3 = 0であるトリプレットです。

アルゴリズム

  1. ソート 指定された配列。
  2. をセットする ブーリアン 変数 見つかった falseに。
  3. i = 0からiへのループ
    1. 作成セッションプロセスで fir = i + 1、sec = n-1 および別の変数 x 現在の配列要素に。
    2. モミながら
      1. 0つの要素が一緒になってXNUMXの合計を形成するかどうかを確認します。
        1. trueの場合、XNUMXつの数値すべてを出力し、isFoundをtrueに設定します。
      2. 0つの要素(現在の配列要素)の合計がXNUMX未満かどうかを確認します。
        1. trueの場合、firの値を1増やします。
      3. 0つの要素の合計がXNUMXより大きいかどうかを確認します。
          1. trueの場合、secの値を1減らします。
  4. isFoundがfalseのままであるかどうかを確認します。これは、トリプレットを形成できないことを意味します。

説明

配列が与えられます。 次に、合計が0の配列内の指定された数で形成できるトリプレットを決定するように求められます。ネストされたループを使用します。 このアルゴリズムは、一定の空間で機能します。 まず、配列を並べ替えます。 このようにして、0ポインター手法を使用できます。 最初にXNUMXつのブール変数を宣言し、その値をfalseに設定します。 これは、要素の合計がXNUMXであるトリプレットが見つからない場合に、次の値を確認するためです。 見つかった 誤りのままです。 次に、トリプレットが見つかったときにtrueに更新します。 したがって、これにより、トリプレットは見つからないと結論付けることができます。

ネストされたループで、最初に配列を並べ替えます。 次に、配列をn-1までトラバースします。 開始値をi + 1に設定し、最後の値をn-1に設定し、xを外側のループの現在の値に設定します。 内側のループでは、配列の値をトラバースし、0つの要素すべての合計(x + arr [fir] + arr [sec])が0に等しいかどうかを確認します。 XNUMXであることがわかった場合、それは最初のペアを見つけて配列の現在の値をすべて出力し、isFound値をtrueに設定したことを意味します。

これは、ペアの0つが見つかったことを示します。 トリプレットの合計が0に等しくない場合。0つの現在の要素の合計が0未満であるかどうかを確認します。合計がXNUMX未満の場合。firをインクリメントすると、開始値が増加します。 条件が満たされない場合。 合計がXNUMXより大きいかどうかを確認します。trueの場合は、秒をデクリメントします。

このようにして、合計が0になる可能性のあるすべてのトリプレットを見つけます。

合計がゼロのすべてのトリプレットを検索するC ++コード

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

合計がゼロのすべてのトリプレットを検索するJavaコード

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

複雑さの分析

時間の複雑さ

オン2) where 「n」  配列内の要素の数です。 O(n)時間に寄与する2つのポインター手法を使用しているため。 ただし、この手法自体はO(n)時間使用されます。 したがって、アルゴリズムをO(n ^ XNUMX)時間で実行します。

スペースの複雑さ

O(1) 余分なスペースは必要ありません。