Пронајдете четири елементи што се собираат на дадена вредност (Hashmap)


Ниво на тешкотија Тешко
Често прашувано во Амазон Google Мајкрософт
Низа Хаш Сортирање

Проблемот „Пронајди четири елементи што сумираат во дадена вредност (Hashmap)“ вели дека претпоставуваш дека имаш цела низа и број наречен збир. Со изјавата за проблем се бара да се утврди дали има четири елементи присутни во низата што се сумира на дадената вредност „збир“. Ако е точно, тогаш излезете од функциите „Да“, инаку излези „Не“.

пример

Пронајдете четири елементи што се собираат на дадена вредност (Hashmap)

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 и проверете дали сума-вал постои во табелата за хаш.
        1. Ако е точно, тогаш земи го клучот и дознај го бројот и врати го вистинитиот.
      2. Друго, ставете ги i и j во табелата со хаш заедно со клучот како arr [i] + arr [j].
  2. Врати неточно.

Објаснување

Дадена ни е изјава за проблем што бара да утврдиме дали постојат четири елементи што постојат во низата што ја сумира дадената вредност. Ако да, тогаш следи, тогаш функцијата треба да печати да, инаку печати не. Е користиме хашинг за да се реши овој проблем. Заради тоа, можеме да го зачуваме клучот како наш елемент што се спојува за да биде можната под-низа, и вредноста како наши индекси за тоа, така што ќе можеме да провериме на тоа.

Да разгледаме пример:

пример

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, збир = 25

Тука зедовме пример. Ние прогласивме А. Булова функција што ќе се врати вистинита и неточна. Ние исто така ќе користиме својство на објект за кои предмети ќе користиме, во нашата мапа, бидејќи еден од нашите аргументи е кој било список или вектор. Значи, во основа ќе ги пресечеме низите, но земајќи го секој елемент од низата истовремено во надворешна јамка и поминувајќи низ остатокот од елементите што доаѓаат еден индекс напред, со втората внатрешна јамка.

Го земаме збирот на двата елементи што е arr [i] + arr [j] и го зачувуваме во некоја променлива наречена val и потоа проверуваме дали збирот-val е присутен во хаштабилни или не, ако не е присутно, тогаш едноставно туркај ги елементите во картата, да претпоставиме дека имаме елементи 2 и 7 од низата (arr [i] и arr [j]), збирот е 9, а збирот 25-9 е 18 е не е присутно во табелата за хаш, така што ние едноставно притискаме 9 и индекси на струја што се 0 и 1, така што подоцна можеме да откриеме дали е присутен збир-arr [i] + arr [j] или не во табелата. Доколку е присутно, тогаш едноставно земете ги вредностите на клучот и проверете некои услови на него, ако е задоволен, тогаш вратете точно. Тоа значи дека го најдовме нашиот одговор.

C ++ код за да пронајдете четири елементи што се собираат на дадена вредност (Hashmap)

#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

Java код за да пронајдете четири елементи што се собираат на дадена вредност (Hashmap)

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 парови што треба да бидат зачувани на картата. Така, комплексноста на вселената е полином.