두 개의 정렬되지 않은 배열이 주어지면 합계가 x 인 모든 쌍을 찾습니다.

난이도 쉽게
자주 묻는 질문 아마존 Facebook
배열 해시 해싱조회수 49

문제 정책

두 개의 정렬되지 않은 배열, 합계가 x 인 모든 쌍을 찾으십시오. 문제는 정렬되지 않은 두 개의 정수 배열과 sum이라는 값이 주어 졌다는 것을 나타냅니다. 문제 설명은 총 쌍 수를 찾아서 sum이라는 주어진 값에 합산되는 모든 쌍을 인쇄하도록 요청합니다.

arr1[] = { 3,6,1,4,8,2}

arr2[] = { 2,1,5,7,2,4}

sum = 9
(8, 1), (4, 5) (2, 7)

설명 : 세 쌍 모두 주어진 값 9와 동일한 합계를 갖는 숫자를가집니다.

arr1[] = { 2,5,1,7,9}

arr2[] = { 3,6,8,1,0}

sum = 7
(1, 6), (7, 0)

설명 : 두 쌍 모두 주어진 값 7과 같은 합계를 갖는 숫자를가집니다.

두 개의 정렬되지 않은 배열에서 sum = x 인 모든 쌍을 찾는 알고리즘

1. Declare a Set.
2. Insert all the values of array1 into the Set.
3. Traverse the array2.
4. Check if the difference of sum and each number of array2 is present in a set.
5. If present then prints the difference and the current array element.

설명

두 개의 정렬되지 않은 배열이 주어지면 합계가 x 인 모든 쌍을 찾습니다. 이를 위해 우리는 세트를 사용할 것입니다. 세트는 공통 요소를 제거하는 기능도 제공합니다. 우리가 할 일은 array1의 모든 값을 세트에 삽입하는 것입니다. 여기서 설정하면 요소가 제거되거나 제거되지 않습니다. 쌍이 형성 될 수 있는지 확인하기 위해 번호 만 필요하기 때문에 우리는 그다지 신경 쓰지 않습니다.

첫 번째 배열을 순회하는 동안 모든 값을 세트에 삽입합니다. 나중에이 세트를 사용하여 합이 sum이라고하는 주어진 값과 동일한 쌍을 형성 할 수 있는지 확인합니다. 모든 값을 세트에 삽입하면 배열 2를 순회합니다.

두 번째 배열의 첫 번째 요소에서 시작하여 탐색하는 동안 주어진 값과 두 번째 배열의 각 값의 차이를 확인합니다. 두 개의 숫자를 더할 수있는 것과 비슷합니다. a + b = c, 그리고 이제 b와 c 만 있으면 cb로 'a'를 찾을 수 있습니다. 똑같은 것이 여기에 우리는 쌍을 완성하는 데 필요한 값을 찾을 수있는 결과 값이 있습니다. 이것이 우리가 array2에서 array1의 합계와 각 값의 차이를 찾는 이유입니다. 쌍을 찾으면 단순히 쌍과 현재 배열 요소의 차이를 인쇄하면 이것이 필요한 쌍이됩니다.

두 개의 정렬되지 않은 배열이 주어지면 합계가 x 인 모든 쌍을 찾습니다.

암호

두 개의 정렬되지 않은 배열에서 sum = x 인 모든 쌍을 찾는 C ++ 코드

#include<iostream>
#include<unordered_set>

using namespace std;

void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
{
    unordered_set<int> MAP;
    for (int i = 0; i < l1; i++)
        MAP.insert(arr1[i]);

    for (int j = 0; j < l2; j++)
        if (MAP.find(sum - arr2[j]) != MAP.end())
            cout << sum - arr2[j] << " "<< arr2[j] << endl;
}
int main()
{
    int arr1[] = { 3,6,1,4,8,2};
    int arr2[] = { 2,1,5,7,2,4};
    int sum = 9;
    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);
    getPairsofSum(arr1, arr2, l1, l2, sum);
    return 0;
}
8 1
4 5
2 7

 

두 개의 정렬되지 않은 배열에서 sum = x 인 모든 쌍을 찾는 Java 코드

import java.util.HashMap;

class PairofSumUnsortedArray
{
    public static void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        for (int i = 0; i < l1; i++)
            MAP.put(arr1[i], 0);

        for (int j = 0; j < l2; j++)
            if (MAP.containsKey(sum - arr2[j]))
                System.out.println(sum - arr2[j] + " " + arr2[j]);
    }
    public static void main(String[] args)
    {
        int arr1[] = { 3,6,1,4,8,2};
        int arr2[] = { 2,1,5,7,2,4};
        int sum = 9;
        getPairsofSum(arr1, arr2, arr1.length, arr2.length, sum);
    }
}
8 1
4 5
2 7

 

복잡성 분석

시간 복잡성

O (최대 (n, m)) 어디에 "엔""엠" 첫 번째 및 두 번째 배열의 길이입니다.

공간 복잡성

O (최대 (n, m)) 어디에 "엔""엠" 첫 번째 및 두 번째 배열의 길이입니다.

Translate »