Two Sum Coding Problem

I am currently going to school for computer science, and that means that I have to get good at the 1s and 0s of the world. Naturally, I have turned to the same website every other aspiring computer scientist has to work on my coding skills: Leetcode. Today, I will be explaining one of the easiest problems on the website, Two Sum. This is the one that you should definitely begin with if you are trying to dip your feet into coding; it is simple, but it contains a lot of the overarching issues that will commonly come up.

The description of the problem is as follows:

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

So, we need to find a way to iterate through the array and find a position and its complement that add up to the target and return those two targets. The simplest way of doing this is to create a double for loop. One that chooses the first position and one that loops through the array checking each position to the initial one.

This would work, but it is extremely slow. This solution has a time complexity of n-squared where n is the number of Integers in the given array (nums). To solve this quickly in a time of 2n, we need to use a HashMap.

A HashMap is a data structure that contains values that are labeled by keys. Each value is assigned a key when it is added to the HashMap, and that key can be used to instantly get the value, skipping a ton of processing. In this case, if we use the complement of the current position we are looking at (which can be written as the target – the value at that position) as the key and store the current position as the value, we will be able to then loop through the array once more and simply check if the complement exists for that value. If it does, return the current position and the complement’s position. Problem solved!

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> data = new HashMap<>();
        for (int index = 0; index < nums.length; index++)
            data.put(target - nums[index], index);
        int[] solution = new int[2];
        for (int i = 0; i < nums.length; i++){
            if (data.containsKey(nums[i]) && data.get(nums[i]) != i){
                solution[0] = data.get(nums[i]);
                solution[1] = i;
            }
                

        }
        return solution;
    }
}