# Two Sum

By [wy](https://paragraph.com/@wy-2) · 2023-06-07

---

Problem Description
-------------------

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.

**Example 1:**

    Input: nums = [2,7,11,15], target = 9
    Output: [0,1]
    Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
    

**Example 2:**

    Input: nums = [3,2,4], target = 6
    Output: [1,2]
    

**Example 3:**

    Input: nums = [3,3], target = 6
    Output: [0,1]
    

**Constraints:**

*   `2 <= nums.length <= 104`
    
*   `-109 <= nums[i] <= 109`
    
*   `-109 <= target <= 109`
    
*   **Only one valid answer exists.**
    

Solution
--------

### Brute Force

The easiest way to solve this problem is to iterate through each number of the array `i` , for each `i` , check every other number `j` in the array, sum them up and compare with `target` to find out the answer. But this is a  `O(n^2)`time complexity which is not optimal at all.

### Hashmap

One optimal solution would be utilizing the feature of `hashmap`, here goes the java code

    public class TwoSum {
        int[] solution(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int diff = target - nums[i];
                if (map.get(diff) != null && map.get(diff) != i) {
                    return new int[]{i, map.get(diff)};
                }
                map.put(nums[i], i);
            }
            return new int[] {0, 0};
        }
    }
    

Cheers !

---

*Originally published on [wy](https://paragraph.com/@wy-2/two-sum)*