Rayանկից գտեք տարրերի զույգ, որի գումարը հավասար է թվին


Գրիր ծրագիր `զանգվածում զույգ գումար գտնելու համար` տրված մուտքային համարին հավասար:

Airույգ գումարը հավասար է տրված թվին

[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]

Timeամանակի բարդությունը. O (NlogN)
Տիեզերական բարդություն: Ո (1)
Հայեցակարգ

Ասենք, որ ներքևում թվեր կան, և մենք պետք է զանգվածից գտնենք 2 թվեր, որոնց գումարը հավասար է 17-ի

-1 5 7 -8 12 16 -30 -4
Եվ մենք պետք է գտնենք մի զույգ, որի գումարը ասենք 17 է

Ստորև ներկայացված տեսանյութում բացատրվում է զանգվածից մի թվերի զույգ գտնելու ալգորիթմը, որի գումարը պետք է հավասար լինի տրված մուտքային թիվ 17-ին

Ապա արդյունավետ եղանակը ցույց է տրված ստորև

1. Թվերը դասավորիր աճման կարգով (տեսակավորիր)

2. Գործարկել մի օղակ այս եղանակով.

  • Ասենք, որ զանգվածի սկզբում կանգնած է մեկ մարդ, իսկ վերջում `երկրորդ
  • Նրանք գումարում են այն թվերը, որոնց վրա նրանք կանգնած են => -30 +16 = 14
  • Եթե ​​նրանց թիվը հավասար է տրված X թվին, ապա նրանք վայելում են
  • Այլապես, եթե գումարը պակաս է տրված թվից, նրանք խնդրում են, որ զանգվածի սկզբում կանգնած առաջին անձը մեկ քայլ շարժվի դեպի վերջ, որովհետև եթե նա ճիշտ ճանապարհորդի, ապա թիվն ավելանում է, և, հետեւաբար, գումարը:
  • Նմանապես, եթե գումարը ավելի շատ է, ապա վերջում գտնվող անձին խնդրում են մեկ քայլով շարժվել դեպի մեկնարկ
  • Մենք կրկնում ենք այնքան ժամանակ, քանի դեռ անձինք չեն բախվել, քանի որ դրանից հետո նույն զույգերը կստացվեն:
  • Եթե ​​նման զույգ չգտնվի, երկուսն էլ տխրում են:
Կարևոր է Տեսակավորել () գործառույթը: Մենք պետք է օգտագործենք Merge կամ Heap տեսակավորումը, քանի որ դրանք O (NLogN) ժամանակ են պահանջում: Հակառակ դեպքում մենք կարող ենք օգտագործել տեսակավորելու () 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]

Timeամանակի բարդություն - Ո (NlogN)
Տիեզերական բարդություն - ՎՐԱ)
Հայեցակարգ

Ասենք, որ զանգվածում կան թվեր, և մենք պետք է զանգվածից գտնենք երկու տարրերի բազմություն, որի գումարը հավասար է մուտքի թիվ 23-ի:

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

և մենք պետք է գտնենք մի զույգ, որի գումարը ասենք 23

Այս հայեցակարգը հիմնված է քարտեզագրման մոտեցման վրա `զանգվածից զույգ գտնելու տարրեր, որոնց գումարը հավասար է թվին

1. Ստեղծեք քարտեզ այնպես, որ յուրաքանչյուր տարր ավելացվի:
2. Եթե գոյություն ունի X զույգ գումարող զույգ, ապա երկու տարրերն էլ առկա են քարտեզում:
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-ը այս հարցի լուծման լավագույն միջոցն է: