Write a program that find all the pairs that add up to given number?

Question

Write a program which finds all pairs of elements in an array whose sum is equal to a given number

Input  array: [-2,1,3,5,6,7,8,10,12,15,17,19,20]
Sum : 20

Output

6, 12
3, 15
1, 17
-2, 20
8, 10

Required best time complexity and effective code

Answer 1

The easiest way can be the below solution whose time complexity is O(n^2). Might not recommended for large arrays.

static void getPairsEasy(int[] ar, int sum) {
        for (int i = 0; i < ar.length; i++)
            for (int j = i + 1; j < ar.length; j++) {
                if (sum == ar[i] + ar[j])
                    System.out.println(ar[i] + "," + ar[j]);
            }
    }

The other solution could be below, whose time complexity is O(nLogn). Works only for sorted arrays.

    static void getPairsBinarySearch(int[] ar, int sum) { 
        Arrays.sort(ar);
        int i=0, j = ar.length - 1;
        while(i<j){
            if(sum==ar[i]+ar[j]){
                System.out.println(ar[i]+","+ar[j]);
                i++; j--;
            }else if(sum > ar[i]+ar[j]){
                i++;
            }else if(sum < ar[i]+ar[j]){
                j--;
            } 
        }
    }