Verilmiş cəm ilə cütlük sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon Məlumat dəsti Piyada çox yol qət eləmək
Geyim Hashing Riyaziyyat çeşidləyiciBaxılıb 29

“Verilən cəm ilə say cütü” problemində bir tam ədədi vermişik array[] və başqa bir rəqəm 'cəm' deyərsə, verilmiş bir massivdəki hər iki elementdən birinin cəmi 'yə bərabər olub olmadığını təyin etməlisiniz.

misal

Input:

arr [] = {1,3,4,6,7} və cəmi = 9.

Çıxış:

“Verilmiş elementlər tapıldı cəmi ”olduğu üçün cəmi bərabər olan '3' və '6' olduğu üçün '9' a.

Input:

arr [] = {11,3,5,7,10} və cəmi = 20.

Çıxış:

Cəmi '8' -ə bərabər olan hər hansı bir rəqəm olmadığı üçün "verilmiş cəm ilə elementlər tapılmadı".

Alqoritm

  1. Bəyan edin a təyin etmək.
  2. 0-dan 'i' -ə qədər isə massivin uzunluğundan azdır.
    1. J-cəmini [i] cəminə qoyun.
    2. Dəstin 'j' olub olmadığını yoxlayın, doğrudursa j və arr [i] yazdırın, bu cüt olacaq.
    3. Başqa bir sıra [i] çoxluğa əlavə edin.

Izahat

Bir problem ifadəsi verdik, burada tam ədədlər massivi və bir rəqəm 'cəm' deyilir. Bizim tapşırığımız, bir verilişin verilmiş “cəm” ə bərabər bir cəmi olan iki elementdən birinin olub olmadığını müəyyənləşdirməkdir.

Əsas fikrimiz HashSet istifadə etmək və bir cüt tapmaqdır. Keçid zamanı cəmin fərqi və sıra dəyərinin hər birini saxlayacağıq, çünki cütlükdə bu iki element var və verilən cəm başqa bir element tapmaq üçün açardır, buna görə də bütün sıra elementlərini çoxluğa saxlayırıq. və cütlükdəki elementlərdən birinin ya mövcud olub olmadığına baxın.

Bunu öyrənmək üçün bir qarma üsulundan istifadə edəcəyik.

Bir nümunə götürək:

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

  • i = 0, myset, cəmi = 16;

j = cəm-arr [i];

yəni j = 16-1 = 15 və şübhəsiz 'j' bir xəritədə olmayacaqdır.

Beləliklə, myset-ə '1' olan arr [i] əlavə edin.

  • i = 1, myset = {1}, cəmi = 16;

j = cəm-arr [i];

yəni j = 16-4 = 12 və şübhəsiz 'j' xəritədə yoxdur.

Beləliklə, myset-ə '4' olan arr [i] əlavə edin.

  • i = 2, myset = {1, 4}, cəmi = 16;

j = cəm-arr [i];

yəni j = 16-45 = -29 və şübhəsiz 'j' bir xəritədə olmayacaqdır.

Beləliklə, myset-ə '45' olan arr [i] əlavə edin.

  • i = 3, myset = {1, 4, 45}, cəmi = 16;

j = cəm-arr [i];

yəni j = 16-6 = 10 və j xəritədə yoxdur.

Beləliklə, myset-ə '6' olan arr [i] əlavə edin.

  • i = 4, myset = {1, 4, 45, 6}, cəmi = 16;

j = cəm-arr [i];

yəni j = 16-10 = 6 və j xəritədə mövcuddur.

Cütlüyün başqa bir elementini tapdığımız yerdir. Artıq 16 və 10-da əməliyyat etdik.

Və çap edirik:

“Verilmiş cəmi 16 olaraq tapılan elementlər (10, 6);

Yəni cəmdə “cəm” ə bərabər olan elementlərdən ikisi massivdə mövcuddur.

Həyata keçirilməsi

Verilən Cəm ilə Qraf cütü üçün C ++ proqramı

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

Verilən Cəm ilə Qraf cütü üçün Java proqramı

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)

Verilən cəm ilə say cütü üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) çünki bütün sıra yalnız bir dəfə keçilməlidir.

Kosmik Mürəkkəblik

O (n) massiv elementlərini saxlamaq üçün bir hash xəritəsi istifadə edilmişdir.

arayış

Translate »