Двойка за броене с дадена сума


Ниво на трудност Лесно
Често задавани в Аколит Амазонка FactSet Екскурзия
Array хеширане Математически сортиране

В проблем „брой двойка с дадена сума“ сме дали цяло число масив[] и друго число казва „сума“, трябва да определите дали някой от двата елемента в даден масив има сума, равна на „сума“.

Пример

Вход:

arr [] = {1,3,4,6,7} и сума = 9.

Изход:

„Намерени елементи с даденото сума “, тъй като има„ 3 “и„ 6 “, които имат сума равна до '9'.

Вход:

arr [] = {11,3,5,7,10} и сума = 20.

Изход:

„Елементи не са намерени с дадената сума“, тъй като няма число, което да има сума, равна на „8“.

алгоритъм

  1. Декларирайте а определен.
  2. Докато 0 до 'i' е по-малко от дължината на масива.
    1. Задайте j на sum-arr [i].
    2. Проверете дали комплектът съдържа 'j', ако е вярно, тогава отпечатайте j и arr [i], това ще бъде двойката.
    3. В противен случай добавете arr [i] в ​​комплекта.

Обяснение

Дадохме изявление за проблем, в което получаваме масив с цели числа и число, което казва „сума“. Нашата задача е да определим дали масивът има някой от двата елемента, които имат сумиране, равно на дадена „сума“.

Основната ни идея е да използваме HashSet и да намерим чифт. За което ще съхраняваме разликата в сумата и всяка стойност на масива, докато обхождаме, защото една двойка има тези два елемента и дадена сума е ключът за намиране на друг елемент, затова съхраняваме всички елементи на масива в набора и разгледайте дали един от елементите в двойка присъства или не.

За да го разберем, ще използваме метод за хеширане.

Нека вземем пример:

arr [] = {1, 4, 45, 6, 10, 8};

  • i = 0, myset, сума = 16;

j = сума-arr [i];

това е j = 16-1 = 15 и със сигурност 'j' няма да присъства в карта.

Така че добавя arr [i], който е '1' в myset.

  • i = 1, myset = {1}, сума = 16;

j = сума-arr [i];

това е j = 16-4 = 12 и със сигурност 'j' не присъства в карта.

Така че добавя arr [i], който е '4' в myset.

  • i = 2, myset = {1, 4}, сума = 16;

j = сума-arr [i];

това е j = 16-45 = -29 и със сигурност 'j' няма да е в карта.

Така че добавя arr [i], който е '45' в myset.

  • i = 3, myset = {1, 4, 45}, сума = 16;

j = сума-arr [i];

това е j = 16-6 = 10 и j не присъства в карта.

Така че добавя arr [i], който е '6' в myset.

  • i = 4, myset = {1, 4, 45, 6}, сума = 16;

j = сума-arr [i];

това е j = 16-10 = 6 и j присъства в картата.

Тук намираме друг елемент на двойка. Вече направихме операция на 16 и 10.

И ние отпечатваме:

„Намерени елементи с дадената сума 16, е (10, 6);

Това означава, че два от елементите присъстват в масива, който има сума, равна на „сума“.

изпълнение

C ++ програма за Count двойка с дадена сума

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}
Found elements with the given sum as 16 is (10, 6)

Java програма за брой двойка с дадена сума

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

Анализ на сложността за двойка броя с дадена сума

Сложност във времето

О (п) тъй като целият масив е необходим, за да бъде преминат само веднъж.

Сложност на пространството

О (п) тъй като хеш картата е била използвана за съхраняване на масивни елементи.

препратка