1. Two Sum

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

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

You can return the answer in any order.

Thoughts

• Immediately I know that this is possible using nested for-loops, but that isn't an efficient solution as it achieves an O(n²) runtime complexity

  • I will implement it like this anyway before trying to optimize

    •   class Solution {
            public int[] twoSum(int[] nums, int target) {
                int[] ans = new int[2];
                for (int i = 0; i < nums.length; i++) {
                    for (int j = 0; j < nums.length; j++) {
                        if (j == i) continue;
                        if (nums[i] + nums[j] == target) {
                            ans[0] = i;
                            ans[1] = j;
                        }
                    }
                }
                return ans;
            }
        }
      

    • Almost certain there is a faster way

• I think using a Map would potentially be a good way to do this

  • It would take O(n) to add all of the numbers to a Map, then another O(n) to find the correct other term, so overall O(n)

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> newNums = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            newNums.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            if (newNums.getOrDefault(target - nums[i], -1) != -1) {
                if (i == newNums.get(target - nums[i])) continue;
                return new int[]{i, newNums.get(target - nums[i])};
            }
        }

        return new int[2];
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

Conclusion

Finally completed the infamous Two Sum. These are the types of problems that I like, where there is a really simple solution that is immediately obvious, but there are more complex solutions that are much better in a variety of ways.