주어진 값 (Hashmap)에 합산되는 XNUMX 개의 요소 찾기


난이도 하드
자주 묻는 질문 아마존 구글 Microsoft
배열 해시 정렬

"주어진 값 (해시 맵)에 합산되는 XNUMX 개의 요소 찾기"문제는 정수 배열과 sum이라는 숫자가 있다고 가정합니다. 문제 설명은 주어진 값 "sum"을 합산하는 XNUMX 개의 요소가 배열에 있는지 확인하도록 요청합니다. 참이면 함수는“예”를 출력하고 그렇지 않으면“아니오”를 출력합니다.

주어진 값 (Hashmap)에 합산되는 XNUMX 개의 요소 찾기

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

암호알고리즘

  1. 루프를 가로 질러 동안 나는 <n – 1.
    1. 루프를 가로 질러 j = i + 1 <n 동안
      1. arr [i] + arr [j] 값을 val에 저장하고 sum-val이 해시 테이블에 있는지 확인합니다.
        1. true이면 키를 가져 와서 숫자를 찾은 다음 true를 반환합니다.
      2. 그렇지 않으면 arr [i] + arr [j]와 같은 키와 함께 해시 테이블에 i와 j를 넣습니다.
  2. 거짓을 반환합니다.

설명

주어진 값을 합산하는 배열에 존재하는 XNUMX 개의 요소가 있는지 확인하는 문제 설명이 주어집니다. 그렇다면 함수는 yes를 인쇄하고 그렇지 않으면 no를 인쇄해야합니다. 우리는 사용할 것입니다 해싱 이 문제를 해결하기 위해. 그 때문에 가능한 하위 배열이되도록 짝을 이루는 요소로 키를 저장할 수 있고, 확인할 수 있도록 해당 인덱스로 값을 저장할 수 있습니다.

예를 들어 보겠습니다.

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, 합계 = 25

여기서 우리는 예를 들었습니다. 우리는 부울 true와 false를 반환 할 함수입니다. 또한 인수 중 하나가 목록이나 벡터이기 때문에 맵에서 사용할 객체의 객체 속성을 사용할 것입니다. 그래서 기본적으로 우리는 배열을 순회 할 것이지만, 외부 루프에서 한 번에 배열의 각 요소를 취하고 두 번째 내부 루프를 사용하여 한 인덱스 앞에 오는 나머지 요소를 순회합니다.

arr [i] + arr [j] 인 두 요소의 합계를 가져와 val이라는 변수에 저장 한 다음 sum-val이 해시 테이블 존재하지 않는 경우 단순히 요소를 맵에 푸시합니다. 배열의 요소 2와 7 (arr [i] 및 arr [j])이 있고 합계가 9이고 sum-val 인 25-9가 18이라고 가정합니다. 해시 테이블에 존재하지 않기 때문에 9와 0과 1의 현재 인덱스를 간단히 푸시하여 나중에 sum-arr [i] + arr [j]가 테이블에 있는지 여부를 확인할 수 있습니다. 존재하는 경우 키의 값을 가져 와서 일부 조건을 확인하고 만족하면 true를 반환합니다. 우리가 답을 찾았다는 뜻입니다.

주어진 값 (Hashmap)에 합산되는 XNUMX 개의 요소를 찾는 C ++ 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

주어진 값 (Hashmap)에 합산되는 XNUMX 개의 요소를 찾는 Java 코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

복잡성 분석

시간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. HashMap을 사용하면이 시간 복잡성을 달성 할 수있었습니다. 그렇지 않으면 불가능했을 것입니다.

공간 복잡성

의 위에2어디에 "엔" 배열의 요소 수입니다. 최악의 경우 맵에 저장해야하는 N ^ 2 쌍이있을 수 있습니다. 따라서 공간 복잡성은 다항식입니다.