Берілген қосындымен жұпты санау


Күрделілік дәрежесі оңай
Жиі кіреді Акколит Amazon Деректер жинағы жорық
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-ді [i] қосындысына орнатыңыз.
    2. Жиында 'j' бар-жоғын тексеріңіз, егер рас болса, онда j және arr [i] -ді басып шығарыңыз, бұл жұп болады.
    3. Жиынға [i] arr-ны қосыңыз.

Түсіндіру

Біз есептер шығардық, онда бізге бүтін сандар жиыны және сан қосындысы беріледі. Біздің міндетіміз - массивтің қосындысы берілген «қосындыға» тең екі элементтің кез келгені бар-жоғын анықтау.

Біздің басты идеямыз - HashSet-ті пайдалану және жұп табу. Бұл үшін біз жиынның айырымы мен массивтің әр мәнін өтпелі уақытта сақтаймыз, өйткені жұпта екі элемент бар, ал берілген қосынды басқа элементті табудың кілті болып табылады, сондықтан біз жиымның барлық элементтерін жинаймыз және жұптағы элементтердің біреуі болса немесе жоқ болса, оны қарастырыңыз.

Мұны білу үшін біз хэштеу әдісін қолданамыз.

Мысал алайық:

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

  • i = 0, myset, sum = 16;

j = қосынды-arr [i];

яғни j = 16-1 = 15, және 'j' картада болмайды.

Сонымен, myset-ке '1' болатын arr [i] қосады.

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

j = қосынды-arr [i];

яғни j = 16-4 = 12 және 'j' картада жоқ.

Сонымен, myset-ке '4' болатын arr [i] қосады.

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

j = қосынды-arr [i];

яғни j = 16-45 = -29, және 'j' картада болмайды.

Сонымен, myset-ке '45' болатын arr [i] қосады.

  • i = 3, myset = {1, 4, 45}, sum = 16;

j = қосынды-arr [i];

яғни j = 16-6 = 10, ал j картада жоқ.

Сонымен, myset-ке '6' болатын arr [i] қосады.

  • i = 4, myset = {1, 4, 45, 6}, sum = 16;

j = қосынды-arr [i];

яғни j = 16-10 = 6 және j картада бар.

Бұл жерде біз жұптың тағы бір элементін табамыз. Біз 16 және 10 операцияларды жасадық.

Біз басып шығарамыз:

«Берілген сомасы 16-ға тең элементтер табылды (10, 6);

Бұл жиында «қосындыға» тең болатын екі элемент бар дегенді білдіреді.

Іске асыру

Берілген қосындымен сандық жұпқа арналған C ++ бағдарламасы

#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)

Берілген қосындымен сандық жұптың күрделілігін талдау

Уақыттың күрделілігі

O (N) өйткені бүкіл массивті бір рет қана айналып өту керек.

Ғарыштың күрделілігі

O (N) массив элементтерін сақтау үшін хэш картасы қолданылған.

анықтамалық