Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return
an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can’t add a single integer to itself in order to obtain the
target sum.

Sometimes you need to return the indices of the two numbers instead of the two numbers.

First attempt using 2 for loops

Time complexity: O(n^2)

Space complexity: O(1)

public static int[] twoNumberSum(int[] array, int targetSum) {
    int size = array.length;

    if (size < 2) {
        return new int[0];
    }

    for (int x = 0; x < size; x++) {
        for (int y = 0; y < size; y++) {
            if (x == y) {
                continue;
            }

            if (array[x] + array[y] == targetSum) {
                int[] operands = new int[2];
                operands[0] = array[x];
                operands[1] = array[y];
                return operands;
            }

        }
    }

    return new int[0];
}

Second attempt with a sorted Array

Time complexity: O(nlogn)

Space complexity: O(1)

if space is more important than time, this is the optimal solution.

public static int[] twoNumberSum(int[] array, int targetSum) {

    int size = array.length;

    if (size < 2) {
        return new int[0];
    }

    Arrays.sort(array);

    int left = 0;
    int right = size - 1;

    while (left < right) {
        int sum = array[left] + array[right];

        if (sum == targetSum) {
            return new int[]{array[left], array[right]};
        } else if (sum < targetSum) {
            left++;
        } else if (sum > targetSum) {
            right--;
        }
    }

    return new int[0];
}

Third attempt with a Set

Time complexity: O(n)

Space complexity: O(n)

if time is more important than space, this is the optimal solution.

public static int[] twoNumberSum(int[] array, int targetSum) {

    int size = array.length;

    if (size < 2) {
        return new int[0];
    }

    Map<Integer> nums = new HashMap<>();

    for (int num : array) {
        int match = targetSum - num;
        if (nums.containsKey(match)) {
            return new int[]{match, num};
        } else {
            nums.put(num,num);
        }
    }

    return new int[0];
}

Source code on Github