Given a list of numbers and a number k, return whether any two numbers from the list add up to k

This question can be easily solved with the help of set in O(N) time and space complexity.First add all the elements of array into set and then traverse each element of array and check whether K-ar[i] is present in set or not.

Here is the code in java with O(N) complexity :

boolean flag=false;HashSet<Long> hashSet = new HashSet<>();for(int i=0;i<n;i++){    if(hashSet.contains(k-ar[i]))flag=true;    hashSet.add(ar[i]);}if(flag)out.println("YES PRESENT");else out.println("NOT PRESENT");

Here is a Java implementation with the same time complexity as the algorithm used to sort the array. Note that this is faster than your second idea because we do not need to search the entire array for a matching partner each time we examine a number.

public static boolean containsPairWithSum(int[] a, int x) {    Arrays.sort(a);    for (int i = 0, j = a.length - 1; i < j;) {        int sum = a[i] + a[j];        if (sum < x)            i++;        else if (sum > x)            j--;        else            return true;    }    return false;}

Proof by induction:Let a[0,n] be an array of length n+1 and p = (p1, p2) where p1, p2 are integers and p1 <= p2 (w.l.o.g.). Assume a[0,n] contains p1 and p2. In the case that it does not, the algorithm is obviously correct.

Base case (i = 0, j = n):a[0,-1] does not contain p1 and a[n,n+1] does not contain p2.

Hypothesis:a[0,i-1] does not contain a[i] and a[j+1,n] does not contain p2.

Step case (i to i + 1 or j to j - 1):

1. Assume p1 = a[i]. Then, since p1 + a[j] < p1 + p2, index j must be increased. But from the hypothesis we know that a[j+1,n-1] does not contain p2. Contradiction. It follows that p1 != a[i].
2. j to j - 1 analogously.

Because each iteration, a[0,i-1] and a[j+1,n], does not contain p1, and p2, a[i,j] does contain p1 and p2. Eventually, a[i] = p1 and a[j] = p2 and the algorithm returns true.

This is java implementation with O(n) Time complexity and O(n) space. The idea is have a HashMap which will contain complements of every array element w.r.t target. If the complement is found, we have 2 array elements which sum to the target.

 public boolean twoSum(int[] nums, int target) {    if(nums.length == 0 || nums == null) return false;    Map<Integer, Integer> complementMap = new HashMap<>();    for (int i = 0; i < nums.length; i++) {         int curr = nums[i];         if(complementMap.containsKey(target - curr)){           return true;         }    complementMap.put(curr, i);    }  return false;}