Намерете четири елемента, които сумират дадена стойност (Hashmap)


Ниво на трудност Трудно
Често задавани в Амазонка Google Microsoft
Array Хашиш сортиране

Проблемът „Намерете четири елемента, които сумират дадена стойност (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. Прекоси цикъла, докато i <n - 1.
    1. Прекоси цикъла, докато j = i + 1 <n
      1. Съхранявайте стойността на arr [i] + arr [j] към val и проверете дали sum-val съществува в хеш таблицата.
        1. Ако е вярно, вземете ключа и разберете номера и върнете true.
      2. В противен случай сложете i и j в хеш таблицата заедно с ключа като arr [i] + arr [j].
  2. Връщане на false.

Обяснение

Дадено ни е изявление за проблем, което иска да определи дали в масива съществуват четири елемента, които обобщават дадената стойност. Ако отговорът е „да“, след това следвайте функцията, която трябва да отпечата „да“, в противен случай отпечатайте не. Ще използваме хеширане за решаване на този проблем. Поради това можем да съхраним ключа като наш елемент, който се сдвоява, за да бъде възможният подмасив, и стойност като наши индекси на това, за да можем да го проверим.

Нека разгледаме един пример:

Пример

arr [] = {2, 7, 3, 2, 9, 5, 9, 3}, сума = 25

Тук взехме пример. Обявихме a Булева функция, която ще върне true и false. Също така ще използваме свойството обект на кои обекти ще използваме в нашата карта, тъй като един от аргументите ни е всеки списък или вектор. Така че основно ще прекосим масивите, но вземаме всеки елемент от масив наведнъж във външен цикъл и обхождаме останалите елементи, които идват с един индекс напред, с втория вътрешен цикъл.

Взимаме сумата от двата елемента, която е arr [i] + arr [j], и я съхраняваме в някаква променлива, наречена val и след това проверяваме дали sum-val присъства в hashtable или не, ако не присъства, просто натиснете елементите в картата, да предположим, че имаме елемент 2 и 7 на array (arr [i] и arr [j]), получаването на сума е 9, а sum-val, който е 25-9, е 18 е не присъства в хеш таблицата, затова просто натискаме 9 и текущите индекси, които са 0 и 1, за да можем по-късно да разберем дали sum-arr [i] + arr [j] присъства или не в таблицата. Ако присъства, просто вземете стойностите на ключа и проверете някои условия върху него, ако е изпълнено, върнете true. Това означава, че намерихме своя отговор.

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 двойки, които трябва да се съхраняват в картата. По този начин пространствената сложност е многочленна.