Βρείτε ζεύγη στοιχείων από πίνακα του οποίου το άθροισμα είναι ίσο με τον αριθμό


Γράψτε ένα πρόγραμμα για να βρείτε ένα ζεύγος άθροισμα σε πίνακα ίσο με τον δεδομένο αριθμό εισόδου.

Ζεύγος αθροίσματος ίσο με έναν δεδομένο αριθμό

[vc_row] [vc_column width = "2/3 ″] [td_block_text_with_title custom_title =" Method 1 ″] [/ td_block_text_with_title] [/ vc_column] [/ vc_row]

Χρόνος πολυπλοκότητας: O (NlogN)
Διαστημική πολυπλοκότητα: Ο (1)
Έννοια:

Ας υποθέσουμε ότι υπάρχουν αριθμοί παρακάτω και πρέπει να βρούμε 2 αριθμούς από έναν πίνακα του οποίου το άθροισμα είναι ίσο με 17

-1 5 7 -8 12 16 -30 -4
Και πρέπει να βρούμε ένα ζευγάρι του οποίου το άθροισμα είναι 17

Το παρακάτω βίντεο εξηγεί τον αλγόριθμο για να βρει ένα ζευγάρι αριθμών από έναν πίνακα του οποίου το άθροισμα πρέπει να είναι ίσο με τον δεδομένο αριθμό εισόδου 17

Τότε ο αποτελεσματικός τρόπος φαίνεται παρακάτω

1. Τακτοποιήστε τους αριθμούς σε αύξουσα σειρά (Ταξινόμηση)

2. Εκτελέστε έναν βρόχο με αυτόν τον τρόπο:

  • Ας πούμε ότι ένα άτομο στέκεται στην αρχή του πίνακα και το δεύτερο άτομο στο τέλος
  • Προσθέτουν τους αριθμούς στους οποίους στέκονται => -30 +16 = 14
  • Εάν ο αριθμός τους είναι ίσος με τον δεδομένο αριθμό X τότε απολαμβάνουν
  • Διαφορετικά, εάν το άθροισμα είναι μικρότερο από τον δεδομένο αριθμό, ζητούν από το πρώτο άτομο που στέκεται στην αρχή του πίνακα να μετακινηθεί ένα βήμα προς το τέλος, διότι αν ταξιδεύει σωστά, ο αριθμός αυξάνεται και ως εκ τούτου το άθροισμα.
  • Ομοίως, εάν το άθροισμα είναι περισσότερο, το άτομο στο τέλος καλείται να κινηθεί προς την αρχή με ένα βήμα
  • Επαναλαμβάνουμε έως ότου συγκρουστούν τα άτομα καθώς μετά θα ληφθούν τα ίδια ζεύγη.
  • Εάν δεν βρεθεί τέτοιο ζευγάρι, τότε και οι δύο γίνονται λυπημένοι.
Σημαντικό είναι η συνάρτηση Sort (). Πρέπει να χρησιμοποιήσουμε την ταξινόμηση Merge ή Heap καθώς παίρνουν χρόνο O (NLogN). Ή αλλιώς μπορούμε να χρησιμοποιήσουμε τη λειτουργία sort () STL. με παραμέτρους "ταξινόμηση (arr, arr + size)"

εισόδου:   -3, -4, 10, 0, 3, -2, 15, 3
Αθροισμα:  7
Απάντηση:  -3 και 10

Κωδικός για τον παραπάνω αλγόριθμο στο C ++

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {-3,-4,10,0,3,-2,15,3};
	int size_of_array = sizeof(arr)/sizeof(arr[0]);
	
	//RequiredSum is number to which the pair should sum to
	
	int RequiredSum = 7;
	
	sort(arr,arr + size_of_array); //sort the array

	int startIndex = 0 ,  endIndex = size_of_array - 1 , sum =0; //variables pointing on their respective indices and sum to store sum of the pair

	while(startIndex <endIndex) //We require a pair so 2 elements and hence both elements should be of different indices
	{
		sum = arr[startIndex] + arr[endIndex];
		if( sum == RequiredSum)
		{
			cout << "The numbers are " << arr[startIndex] <<" and " << arr[endIndex] <<endl;
			return 0;
		}

		else if(sum < RequiredSum) //if sum is less then we need to increase the smaller one
			startIndex ++;
		else //if the sum if more we need to decrease the larger number
			endIndex --;
	}
	cout << "No such pair exists.";
	return 0;
}

Δοκίμασέ το

[vc_row] [vc_column width = "2/3 ″] [td_block_text_with_title custom_title =" Method 2 ″] [/ td_block_text_with_title] [/ vc_column] [/ vc_row]

Χρόνος πολυπλοκότητας - O (NlogN)
Διαστημική πολυπλοκότητα - ΕΠΙ)
Έννοια:

Ας υποθέσουμε ότι υπάρχουν αριθμοί σε έναν πίνακα και πρέπει να βρούμε το σύνολο δύο στοιχείων από έναν πίνακα του οποίου το άθροισμα είναι ίσο με τον αριθμό εισαγωγής 23

-1 5 7 -8 12 16 -30 -4

και πρέπει να βρούμε ένα ζευγάρι του οποίου το άθροισμα είναι 23

Αυτή η ιδέα βασίζεται στην προσέγγιση χαρτογράφησης για την εύρεση στοιχείων ζευγών από πίνακα των οποίων το άθροισμα ισούται με τον αριθμό

1. Δημιουργήστε έναν χάρτη έτσι ώστε να προστίθεται κάθε στοιχείο.
2. Εάν υπάρχει ένα ζεύγος που αθροίζει το Χ, τότε και τα δύο στοιχεία υπάρχουν στον χάρτη.
3. Λοιπόν βγαίνουμε μέσω του πίνακα και το κάνουμε αυτό

  • Βρείτε αν το στοιχείο (X - παρόν) υπάρχει στο χάρτη
  • Εάν υπάρχει, τότε εκτυπώστε τον αριθμό.

Μπορείτε να χρησιμοποιήσετε τη δομή δεδομένων χάρτη STL για αυτό το σκοπό. Διαφορετικά, μπορείτε να δημιουργήσετε έναν πίνακα για ευρετηρίαση όπου το ευρετήριο είναι η τιμή του ίδιου του στοιχείου πίνακα. (Αλλά η χρήση πίνακα έχει ένα μειονέκτημα ότι απαιτείται το μέγεθός του.)

ΑΝΑΜΕΝΟΜΕΝΟΣ

εισόδου:   -3, -4, 10, 0, 3, -2, 15, 3
Αθροισμα:  7
Απάντηση:  -3 και 10

Κωδικός για τον παραπάνω αλγόριθμο στο C ++

#include <bits/stdc++.h>
using namespace std;

map <int,int> m;
map<int,int>::iterator it;

int main()
{
	int arr[] = {-3,-4,10,0,3,-2,15,3};
	int size_of_array = sizeof(arr)/sizeof(arr[0]);
	
	//cout << "Enter the number to which the pair should sum to"<<endl; //Let Sum = 7 int x = 7; //cin >> x; // the number to which the sum of pair of elements must be equal

        int x = 7;
	//cin >> x; // the number to which the sum of pair of elements must be equal

	for (int i = 0; i < size_of_array;++i)
	{
		//Scan and add elements into the map
		it = m.find(arr[i]);
		
		if(it == m.end())
			m.insert(make_pair(arr[i],1)); //Add the element in the map and set the count to 1 that represents it is present
	}

	for (int i = 0; i < size_of_array;i++)
	{
			it = m.find((x - arr[i]));  //If we have two numbers say m and n that sums to x then 
		//if we have m and if we find n in the map then we got the numbers.

			if(it != m.end()) //If it exists then we got the pair
			{
				pair<int,int> p = *it; //Obtain the pair so as to reference the 2nd number
				cout << "The numbers are " << arr[i] <<" and " << p.first <<endl;
				return 0;
			}
	}
	
	cout << "No such pair exists.";
	return 0;
}

Δοκίμασέ το

Εδώ συζητήσαμε δύο αλγόριθμους για να βρούμε στοιχεία ζευγαριού από πίνακα των οποίων το άθροισμα ισούται με τον αριθμό. Αυτή είναι μια συχνή ερώτηση σε τεχνικές συνεντεύξεις.

[vc_row] [vc_column width = "2/3 ″] [td_block_text_with_title custom_title =" Συμπέρασμα "] [/ td_block_text_with_title] [/ vc_column] [/ vc_row]

Εάν ο ερευνητής είναι ΟΚ για να χρησιμοποιήσει επιπλέον χώρο, τότε η Μέθοδος 2 είναι η καλύτερη επιλογή για την επίλυση αυτής της ερώτησης. Αλλά εάν δεν σας επιτρέπει να χρησιμοποιήσετε επιπλέον χώρο για τη χρήση του Χάρτη, τότε η Μέθοδος 1 είναι ο καλύτερος τρόπος για να λύσετε αυτήν την ερώτηση.