import java.util.*;
class Main {
public static void main(String[] args) {
final int[] arr1 = new int[] {1, 2, 5, 9};
final int[] arr2 = new int[] {1, 2, 4, 4};
final int sum = 8;
boolean result1 = naiveSolution(arr1, sum);
System.out.println("Result 1 --> " + result1);
boolean result2 = improvedVersion(arr2, sum);
System.out.println("Result 2 --> " + result2);
}
// Time complexity O(n^2)
public static boolean naiveSolution(int[] arr, int sum) {
System.out.println("Naive Solution");
final int len = arr.length;
for (int i =0; i<len-1; i++) {
for (int j=0; j<len; j++) {
if(arr[i] + arr[j] == sum) {
return true;
}
}
}
return false;
}
//Time Complexity O(n)
public static boolean improvedVersion(int[] arr, int sum) {
System.out.println("Improved Version");
final Set set = new HashSet();
final int len = arr.length;
for(int i=0; i < len; i++) {
if (set.contains(arr[i])) {
return true;
}
set.add(sum-arr[i]);
}
return false;
}
}
