You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 001. 两数和 - 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].

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> 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

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)