a + b + c = dとなるような配列内の最大のdを見つけます


難易度 ミディアム
よく聞かれる アコライト Amazon (アマゾン) デリーベリー 狂信者 フォーカイテス 費用無料
配列 ハッシュ

問題文

あなたが持っているとしましょう 配列 of 整数。 入力値はすべて別個の要素です。 「a + b + c = dとなるような配列内の最大のdを見つける」という問題は、すべての要素が互いに異なるa + b + c = dとなるようなセット内の最大の要素 'd'を見つけることを求めています。

arr[] = {1, 4, 6, 8, 11 }
11

説明: 1つの数字a、b、cは4、6、11で、それらの合計はXNUMXです。

arr[] = {2,4,6,10,15 }
No such solution exists.

説明: XNUMXつの数字がないので、合計するとXNUMXつの数字になります。

アルゴリズム

1. Declare a Map.
2. While traversing through the array.
    1. Add and insert the sum of two elements in a map with their indexes in a Map.
3. Set the number to the minimum value of an integer, which we have to find out.
4. Search for the third number in a map by checking the difference of two numbers is present in a map.
5. If true then check if their indexes should not be the same.
6. Check for the maximum of d and the maximum of arr[i] and arr[j] and store it to d.
7. Return d.

説明

考える 整数 配列 異なる整数で構成されます。 私たちの仕事は、その数を合計するXNUMXつの数が存在するような方法で数を見つけることです。 使用します ハッシング。 ハッシュは効率的なソリューションを提供します。 配列をトラバースし、一度にXNUMXつの配列要素を取得し、それらのペアの合計を格納して、それぞれのインデックスにマップします。

a + b + c = dとなるように、dを検索しているため、ペアを保存します。 これの代わりに、a + b = d –cを検索します。 したがって、最初に、ペアとそのインデックスを格納するとき。 マップにd–cが存在するように要素 'd'をチェックできます。 これは、配列をトラバースしてから、XNUMXつの要素を一度に取得することで実行できます。 両方の要素の違いを作成し、マップに存在する場合はその違いを検索します。 これが当てはまる場合は、現在のXNUMXつの要素がインデックス上の前のペアと同じインデックス上にないことを確認してください。

これは、要素のいずれかが同じインデックスで繰り返されるべきではないかどうかを確認するために必要です。繰り返された数はa、b、c、およびdで考慮することができますが、それらのインデックス、つまり同じインデックス上の数自体は考慮されません。 したがって、これらのインデックスの盗用をチェックする必要があります。 ここで、arr [i]とarr [j]の最大値を見つけ、その最大値をdまでチェックして、それらの間の最大値を見つけ、それをdに格納する必要があります。 なぜなら、dはa、b、c、dの間で常に大きいので、XNUMX番目の数dを見つける必要があるため、配列要素の最大値を見つける必要があります。

製品の導入

a + b + c = dとなるような配列内の最大のdを見つけるC ++プログラム

#include<iostream>
#include<unordered_map>

using namespace std;

int getSumThreeNumber(int arr[], int n)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            MAP[arr[i] + arr[j]] = { i, j };
        }
    }
    int d_number = INT_MIN;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int third = abs(arr[i] - arr[j]);

            if (MAP.find(third) != MAP.end())
            {
                pair<int, int> obj = MAP[third];
                if (obj.first != i && obj.first != j && obj.second != i && obj.second != j)
                    d_number = max(d_number, max(arr[i], arr[j]));
            }
        }
    }
    return d_number;
}
int main()
{
    int arr[] = { 1,4,6,8,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = getSumThreeNumber(arr, n);
    if (res == INT_MIN)
        cout << "No such solution exists";
    else
        cout << res;
    return 0;
}
11

a + b + c = dとなるような配列内の最大のdを見つけるJavaプログラム

import java.util.HashMap;

class CheckIndex
{
    int i, j;

    CheckIndex(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
    int checkI()
    {
        return i;
    }

    int checkJ()
    {
        return j;
    }
}

class sumOfThreeElementToD
{

    public static int getSumThreeNumber(int[] arr, int n)
    {
        HashMap<Integer, CheckIndex> map = new HashMap<>();

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                map.put(arr[i] + arr[j], new CheckIndex(i, j));
            }
        }

        int d_number = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int third = Math.abs(arr[i] - arr[j]);

                if (map.containsKey(third))
                {
                    CheckIndex ci = map.get(third);
                    if (ci.checkI() != i && ci.checkI() != j && ci.checkJ() != i && ci.checkJ() != j)
                    {
                        d_number = Math.max(d_number, Math.max(arr[i], arr[j]));
                    }
                }
            }
        }
        return d_number;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 8, 11 };
        int n = arr.length;
        int output = getSumThreeNumber(arr, n);
        if (output == Integer.MIN_VALUE)
            System.out.println("No such solution exists");
        else
            System.out.println(output);
    }
}
11

a + b + c = dとなるような配列内の最大のdを見つけるための複雑さの分析

時間の複雑さ

オン2where 「n」 配列内の要素の数です。 O(1)時間で挿入検索やその他の操作を可能にするHashMapを使用したため、この複雑さを実現しました。

スペースの複雑さ

オン2) where 「n」 配列内の要素の数です。 HashMapは、入力の異なる要素のペアの追加を格納するためです。 このため、アルゴリズムにはXNUMX次空間の複雑さがあります。

参照