The Two Sum Problem -Java edition

This is a first post in a series on solutions written in Java to some beginner common code challenge questions. The solutions written below are not the only solutions. If you have another solution, please leave it in the comments! Today, I am going to tackle the Two Sum problem.

The Problem

Given an array of integer numbers and an integer target, return indices of the two numbers such that they add up to the target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

The solution - brute force/naive

When I first encountered this problem, my initial solution had two loops.

public class TwoSum {

    // Solution
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int x = i + 1; x < nums.length; x++) {
                if (nums[i] + nums[x] == target) {
                    return new int[] { i, x };
                }
            }
        }
        return new int[] {};
    }

    // Test the solution
    public static void main(String[] args) {

        Scanner keyboard = new Scanner(System.in);
        System.out.println("Enter Array length");

        int n = keyboard.nextInt();
        int[] nums = new int[n];
        System.out.println("Enter Array items");

        for(int i = 0; i <n; i++) {
            nums[i] = keyboard.nextInt();
        }

        System.out.println("Enter Target");
        int target = keyboard.nextInt();
        keyboard.close();

        int [] solution = twoSum(nums, target);

        if(solution.length == 2) {
            System.out.println("Solution is: " + solution[0] + ", " + solution[1]);

        }
        else {
            System.out.println("No solution");
        }
    }
}

Example program output:

Enter Array length
4
Enter Array items
2
7
11
15
Enter Target
17
Solution is: 0 3

This works and will solve the problem, but its Big O complexity for time is O(n^2). Why is this? Because in the worst case scenario, the solution has to loop through the list twice. So as the list grows, the solution grows at an exponential rate. The Space complexity is O(1). It is constant because the algorithm does not rely on any additional data structures. See here for more on Big O complexity.
We can do better. Anytime I see a nested loop, it is a flag that causes me to pause and think, is there a more efficient way? Maybe we can only loop through it once.

A Better Approach

    // Solution
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int dif = target - nums[i];
            if (numMap.get(dif) != null) {
                return new int[] { i, numMap.get(dif) };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
    }

// Test code remains the same

This solution obviously gives us a better outcome in Big O time complexity because there is only one loop. No matter how big our inputs get, the worst case will only run through the entire loop once. This gives O(n) (linear) for Big O time complexity. However, we do include a Hash Table data structure in this algorithm, which could be as large as the array input. This gives us the space complexity of O(n). This would be an example of a space-time tradeoff. I personally like the clarity of using the one loop and the Hash Table.

I have found that when running into code that has nested loops, a good question to ask is: "Can I use a dictionary or a map here?" What are some of your tips you have used to solve these types of problems?