> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/mixed-design/two-sum-4-qs/0001.-two-sum.md).

# 0001. Two Sum

Easy  |  Hash Table  |  28 ms (93.73%),  13.4 MB (79.11%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Two Sum](https://leetcode.com/problems/two-sum/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0001-2-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.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `2 <= nums.length <= 10^4`
* `-10^9 <= nums[i] <= 10^9`
* `-10^9 <= target <= 10^9`
* **Only one valid answer exists.**

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
Each number in the list of integers has its own "remain" value by subtracting its value from the target number.

{% hint style="info" %}
Store the remains as key with the index as the value in the hash table.
{% endhint %}

So that we could iterate each element in the list of integers by the index, and then check whether the value of remain exists.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashTable = dict()

        # ==================================================
        #  Array + Hash Table                              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        for i in range(len(nums)):
            remain = target - nums[i]
            
            if remain in hashTable:
                return [i, hashTable[remain]]
            
            # We could overwrite since there is only one solution
            hashTable[nums[i]] = i
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
    
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0 ; i<nums.length ; i++) {
            int remain = target - nums[i];
            
            if(map.containsKey(remain)) {
                return new int[] {i, map.get(remain)};
            }
            
            map.put(nums[i], i);
        }
        
        return null;
    }
}
```

{% endtab %}
{% endtabs %}