Sponsored
Sponsored
This approach involves sorting the data first and then using a two-pointer technique. By sorting, we can simplify the problem as the elements will be in order. The two-pointer method then efficiently checks possible solutions by limiting the number of checks needed.
Time complexity is O(n log n) due to sorting, and space complexity is O(1).
1#include <iostream>
2#include <algorithm>
3#include <vector>
4
5void findPair(std::vector<int> &arr, int sum) {
6 std::sort(arr.begin(), arr.end());
7 int left = 0, right = arr.size() - 1;
8
9 while (left < right) {
10 int current_sum = arr[left] + arr[right];
11
12 if (current_sum == sum) {
13 std::cout << "Pair found: (" << arr[left] << ", " << arr[right] << ")\n";
14 return;
15 }
16 if (current_sum < sum)
17 left++;
18 else
19 right--;
20 }
21 std::cout << "No pair found\n";
22}The solution sorts the array using std::sort. We employ two pointers to examine possible pairs from either end of the sorted array, optimizing the process by systematically narrowing down the possibilities.
This approach uses a hash table (or dictionary) to keep track of the elements and their complements needed to reach the target sum. By utilizing this lookup, we can reduce the problem to a linear time complexity.
Time complexity is O(n) assuming uniform distribution of hash function (no collisions), and space complexity is O(n).
This C solution uses a simple hash table implementation with linear probing for collision resolution, storing elements as they are checked. If their complement (sum - element) is found in the hash table, the pair exists.