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).
1import java.util.Arrays;
2
3public class PairFinder {
4 public static void findPair(int[] arr, int sum) {
5 Arrays.sort(arr);
6 int left = 0, right = arr.length - 1;
7
8 while (left < right) {
9 int current_sum = arr[left] + arr[right];
10
11 if (current_sum == sum) {
12 System.out.println("Pair found: (" + arr[left] + ", " + arr[right] + ")");
13 return;
14 }
15 if (current_sum < sum)
16 left++;
17 else
18 right--;
19 }
20 System.out.println("No pair found");
21 }
22}In this Java solution, the array is sorted with Arrays.sort, and then two pointers are used to smartly trim down to the potential pairings, checking sums and adjusting pointers accordingly.
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).
using System.Collections.Generic;
public class PairFinder {
public static void FindPair(int[] arr, int sum) {
HashSet<int> complements = new HashSet<int>();
foreach (var number in arr) {
int complement = sum - number;
if (complements.Contains(complement)) {
Console.WriteLine($"Pair found: ({number}, {complement})");
return;
}
complements.Add(number);
}
Console.WriteLine("No pair found");
}
}C# offers a HashSet class to properly insert elements and check for complements in linear time. This aids in swift detection of pairs without needing to scan through remaining elements unnecessarily.