Посчитать пару с заданной суммой


Сложный уровень Легко
Часто спрашивают в Акколит Амазонка Набор фактов Поход
массив хеширования Экзамен Математики Сортировка

В задаче «посчитать пару с заданной суммой» мы дали целое число массив[] и другое число означает «сумма», вы должны определить, имеет ли какой-либо из двух элементов в данном массиве сумму, равную «сумме».

Пример

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

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 = сумма-прибл [я];

то есть j = 16-1 = 15 и наверняка j не будет присутствовать на карте.

Таким образом, он добавляет в myset arr [i], который равен «1».

  • i = 1, myset = {1}, sum = 16;

j = сумма-прибл [я];

то есть j = 16-4 = 12 и, конечно же, j отсутствует на карте.

Таким образом, он добавляет в myset arr [i], который равен «4».

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

j = сумма-прибл [я];

то есть j = 16-45 = -29 и наверняка j не будет на карте.

Таким образом, он добавляет в myset arr [i], который равен «45».

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

j = сумма-прибл [я];

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

Таким образом, он добавляет в myset arr [i], который равен «6».

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

j = сумма-прибл [я];

то есть 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)

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

Сложность времени

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

Космическая сложность

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

Справка