Берилген сумма менен жупту эсептөө


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Amazon Factset селсаяктоо
согуштук тизме Hashing Math сорттоо

"Берилген сумма менен эсептөө жупу" маселесинде биз бүтүн санды бердик согуштук тизме[] жана дагы бир санда "сумма" деп айтылганда, берилген массивдеги эки элементтин кайсы биринин суммасы "суммага" барабар экендигин аныкташыңыз керек.

мисал

киргизүү:

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

Output:

“Берилген менен табылган элементтер суммасы "суммасы бар" 3 "жана" 6 "бар болгондуктан '9' чейин.

киргизүү:

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

Output:

"Берилген сумма менен элементтер табылган жок", анткени сумма "8" ге барабар болгон бир дагы сан жок.

Algorithm

  1. Декларация a коюлган.
  2. Ал эми 0 ден "i" массивдин узундугунан аз.
    1. J-сумманы [i] деп койду.
    2. Топтомдо 'j' камтылгандыгын текшериңиз, эгер чын болсо, анда j жана arr [i] басып чыгарыңыз, бул жуп болот.
    3. Арк [i] топтомун курамына кошуңуз.

түшүндүрүү

Биз көйгөйдү чыгардык, анда бүтүндөй массив жана "сумма" деген сан берилген. Биздин милдет - массивде берилген "суммага" барабар болгон эки элементтин бири бар-жогун аныктоо.

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

Аны билүү үчүн, биз хештинг ыкмасын колдонобуз.

Келгиле, бир мисал алып көрөлү:

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

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

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

бул j = 16-1 = 15 жана 'j' картада жок болот.

Ошентип, ал mysetке '1' болгон arr [i] кошот.

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

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

бул j = 16-4 = 12 жана 'j' картада жок.

Ошентип, ал mysetке '4' болгон arr [i] кошот.

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

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

бул j = 16-45 = -29 жана 'j' картада болбойт.

Ошентип, ал mysetке '45' болгон arr [i] кошот.

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

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

бул j = 16-6 = 10 жана j картада жок.

Ошентип, ал mysetке '6' болгон arr [i] кошот.

  • i = 4, myset = {1, 4, 45, 6}, сумма = 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) хэш картасы массив элементтерин сактоо үчүн колдонулган.

шилтеме