ከተሰጠ ድምር ጋር ጥንድ ይቆጥሩ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን ፋርስት ረጅም መንገድ ተንሸራሸረ
ሰልፍ ሃምሽንግ ሒሳብ መደርደር

በችግር ውስጥ “ከተሰጠ ድምር ጋር ቆጠራን ጥምር” ኢንቲጀር ሰጥተናል ደርድር[] እና ሌላ ቁጥር ‹ድምር› ይላል ፣ በተጠቀሰው ድርድር ውስጥ ካሉ ማናቸውም አካላት ውስጥ “ድምር” ጋር እኩል የሆነ ድምር እንዳለው መወሰን አለብዎት።

ለምሳሌ

ግቤት

arr [] = {1,3,4,6,7} እና ድምር = 9።

ውጤት

ከተሰጡት ጋር የተገኙ ንጥረ ነገሮች ድምር ”ድምር እኩል የሆነ‘ 3 ’እና‘ 6 ’እንዳሉ እስከ '9'

ግቤት

arr [] = {11,3,5,7,10} እና ድምር = 20።

ውጤት

ከ “8” ጋር እኩል የሆነ ቁጥር ስለሌለ “በተጠቀሰው ድምር ያልተገኙ ንጥረ ነገሮች”።

አልጎሪዝም

  1. ያውጅ ሀ ስብስብ.
  2. ከ 0 እስከ 'i' ከድርድሩ ርዝመት ያነሰ ቢሆንም።
    1. ወደ ድምር-አር [i] j ያቀናብሩ።
    2. ስብስቡ ‹j› ን መያዙን ያረጋግጡ ፣ እውነት ከሆነ j እና arr [i] ን ያትሙ ፣ ይህ ጥንድ ይሆናል ፡፡
    3. ሌላ “እኔ” ን ወደ ስብስቡ ውስጥ አክል።

ማስረጃ

እኛ የችግር መግለጫ ሰጥተናል ፣ በውስጡም በቁጥር ብዛት እና ‹ድምር› የሚለን ፡፡ የእኛ ተግባር አንድ ድርድር ከተሰጠው “ድምር” ጋር እኩል የሆነ ማጠቃለያ ያላቸው ከሁለቱ አካላት አንዳቸውም እንደሌላቸው መወሰን ነው።

የእኛ ዋና ሀሳብ ሀሽ ሴትን መጠቀም እና ጥንድ መፈለግ ነው ፡፡ እኛ በምንጓዝበት ጊዜ የንድሩን እና የእያንዳንዱን እሴት ልዩነት እናከማቸዋለን ፣ ምክንያቱም ጥንድ እነዚህ ሁለት አካላት አሏቸው እና የተሰጠው ድምር ሌላ አካልን ለማግኘት ቁልፍ ነው ፣ ለዚያም ነው ሁሉንም የቅንጅት አካላት ወደ ስብስቡ ውስጥ የምናስቀምጠው ፡፡ እና በጥንድ ውስጥ ካሉት ንጥረ ነገሮች አንዱ ካለ ወይም ከሌለው ወደ ውስጥ ይመልከቱ።

እሱን ለማጣራት ፣ የሃሺንግ ዘዴን እንጠቀማለን ፡፡

እስቲ አንድ ምሳሌ እንውሰድ-

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

  • i = 0, myset, ድምር = 16;

j = ድምር-arr [i];

ያ j = 16-1 = 15 ነው እናም በእርግጠኝነት 'j' በካርታ ውስጥ አይኖርም።

ስለዚህ ‹1› የሆነውን arr [i] ወደ ማይስሴት ውስጥ ያክላል ፡፡

  • i = 1, myset = {1}, ድምር = 16;

j = ድምር-arr [i];

ያ j = 16-4 = 12 ነው እናም በእርግጠኝነት 'j' በካርታ ውስጥ የለም።

ስለዚህ ‹4› የሆነውን arr [i] ወደ ማይስሴት ውስጥ ያክላል ፡፡

  • i = 2, myset = {1, 4} ፣ ድምር = 16;

j = ድምር-arr [i];

ያ j = 16-45 = -29 ነው እናም በእርግጠኝነት 'j' በካርታ ውስጥ አይኖርም።

ስለዚህ ‹45› የሆነውን arr [i] ወደ ማይስሴት ውስጥ ያክላል ፡፡

  • i = 3, myset = {1, 4, 45} ፣ ድምር = 16;

j = ድምር-arr [i];

ያ j = 16-6 = 10 ነው እና j በካርታ ውስጥ የለም።

ስለዚህ ‹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)

የጃቫ ፕሮግራም ለቁጥር ጥንድ ከተሰጠ ድምር ጋር

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)

ከተቆጠረ ድምር ጋር ለመቁጠር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ሆይ (n) መላው ድርድር አንድ ጊዜ ብቻ ለመሻገር ስለሚያስፈልግ ፡፡

የቦታ ውስብስብነት

ሆይ (n) እንደ ሃሽ ካርታ የድርድር አባላትን ለማከማቸት ጥቅም ላይ ውሏል።

ማጣቀሻ