# 两数和 - Two Sum

## 001. 两数和 - Two Sum

[Hash Tables]

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

### Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````class Solution { public int[] twoSum(int[] nums, int target) { Map map = new HashMap<>(); for(int i = 0; i < nums.length; i++) map.put(nums[i], i); int complement = 0; for(int i = 0; i < nums.length; i++){ complement = target - nums[i]; if(map.containsKey(complement) && map.get(complement) != i) return new int[] {i, map.get(complement)}; } throw new IllegalArgumentException("No two sum solution"); } } ``````

#### 复杂度分析：11ms

• 时间复杂度：O(n)O(n)， 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。
• 空间复杂度：O(n)O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素。

### Other Solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````class Solution { int size = 2048; int[] map = new int[size]; int length = 2047; int index; public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { index = nums[i] & length; if (map[index] != 0) { return new int[] { map[index] - 1, i }; } else { map[(target - index) & length] = i + 1; } } throw new IllegalArgumentException("No two sum solution"); } } ``````

• 时间复杂度：O(n)