a + b + c = d가되도록 배열에서 가장 큰 d 찾기


난이도 중급
자주 묻는 질문 수행자 아마존 배달 광신자 포카이트 무료
배열 해시

문제 정책

당신이 정렬 of 정수. 입력 값은 모두 고유 한 요소입니다. "a + b + c = d가되도록 배열에서 가장 큰 d 찾기"문제는 모든 요소가 서로 다른 a + b + c = d가되도록 집합에서 가장 큰 요소 'd'를 찾아야합니다.

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

설명 : 세 개의 숫자 a, b, c는 1, 4, 6이고 합은 11입니다.

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

설명 : 세 개의 숫자가 없으므로 합계가 숫자입니다.

암호알고리즘

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.

설명

고려 정수 정렬 고유 한 정수로 구성됩니다. 우리의 임무는 그 숫자를 합한 세 개의 숫자가 존재하는 방식으로 숫자를 찾는 것입니다. 우리는 사용할 것입니다 해싱. 해싱은 효율적인 솔루션을 제공합니다. 배열을 탐색하고 한 번에 두 개의 배열 요소를 가져 와서 해당 쌍의 합계를 저장하여 해당 인덱스와 매핑합니다.

d를 검색하기 때문에 a + b + c = d가되도록 쌍을 저장합니다. 대신 a + b = d – c를 검색합니다. 그래서 처음에는 쌍과 인덱스를 저장할 때. d – c가 맵에 존재하도록 요소 'd'를 확인할 수 있습니다. 이는 배열을 순회 한 다음 한 번에 두 개의 요소를 선택하여 수행 할 수 있습니다. 두 요소의 차이를 만들고지도에있는 경우 차이를 검색합니다. 이것이 사실이면 현재 두 요소가 인덱스의 이전 쌍과 동일한 인덱스에 있지 않아야합니다.

이는 동일한 인덱스에서 반복되지 않아야하는 요소가 있는지 확인하는 데 필요합니다. 반복되는 숫자는 a, b, c 및 d에서 고려 될 수 있지만 해당 인덱스는 동일한 인덱스의 숫자 자체가 고려되지 않습니다. 그래서 우리는 그 지표 표절을 확인해야합니다. 이제 우리는 arr [i]와 arr [j]의 최대 값을 알아 내고 그 최대 값을 d로 확인하여 이들 사이의 최대 값을 찾아서 d에 저장해야합니다. 왜냐하면 우리는 네 번째 숫자 d를 찾아야하기 때문에 배열 요소의 최대 값을 찾아야합니다. d는 항상 a, b, c, 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를 찾기위한 복잡도 분석

시간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. O (1) 시간에 삽입 검색 및 기타 작업을 허용하는 HashMap을 사용했기 때문에 이러한 복잡성을 달성했습니다.

공간 복잡성

의 위에2) 어디에 "엔" 배열의 요소 수입니다. HashMap은 입력의 다른 요소 쌍의 추가를 저장하기 때문입니다. 이 때문에 알고리즘은 XNUMX 차 공간 복잡성을 갖습니다.

참고