# 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
        
        * ```java
            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

```java
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.