Кількість пари з заданою сумою


Рівень складності Легко
Часто запитують у Accolite Амазонка Факти Похід
масив Хешування Математика Сортування

У задачі «підрахувати пару з заданою сумою» ми дали ціле число масив[], а інше число говорить "сума", ви повинні визначити, чи має будь-який з двох елементів у даному масиві суму, рівну "сумі".

Приклад

Вхідний сигнал:

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

вихід:

“Елементи, знайдені з даними сума ”, оскільки є '3' і '6', що має суму, рівну до '9'.

Вхідний сигнал:

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

вихід:

«Елементи не знайдені з заданою сумою», оскільки немає жодного числа, яке має суму, рівну «8».

Алгоритм

  1. Заявіть a комплект.
  2. Тоді як від 0 до 'i' менше довжини масиву.
    1. Встановіть j на sum-arr [i].
    2. Перевірте, чи набір містить 'j', якщо true, тоді надрукуйте j та arr [i], це буде пара.
    3. В іншому випадку додайте arr [i] до набору.

Пояснення

Ми дали твердження про проблему, в якому ми отримуємо цілочисельний масив і число, яке говорить "сума". Наше завдання - визначити, чи має масив будь-який із двох елементів, що має підсумовування, рівне даній “сумі”.

Наша основна ідея - використовувати HashSet і знайти пару. Для чого ми будемо зберігати різницю суми та кожного значення масиву під час обходу, оскільки пара має ці два елементи, і дана сума є ключем для пошуку іншого елемента, тому ми зберігаємо всі елементи масиву в наборі і розглянемо його, якщо один із елементів у парі присутній або відсутній.

Щоб це з’ясувати, ми використаємо метод хешування.

Візьмемо приклад:

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

  • i = 0, myset, sum = 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 для пари Count з заданою сумою

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)

Аналіз складності для пари підрахунків із заданою сумою

Складність часу

О (п) оскільки весь масив потрібно пройти лише один раз.

Складність простору

О (п) оскільки хеш-карта була використана для зберігання елементів масиву.

Посилання