Two Sum
給定一個(gè)數(shù)組nums和一個(gè)整數(shù)值target凝垛，返回兩個(gè)數(shù)值（nums數(shù)組下標(biāo)的index），使其所對(duì)應(yīng)的數(shù)組元素疙筹，相加得到目標(biāo)值target沛硅。
附加條件約束：
- 每個(gè)nums數(shù)組和目標(biāo)值，只有一個(gè)解決方案
- 不能使用重復(fù)的值作為解摄狱，eg: 列子 Example 2中 目標(biāo)值是6脓诡， 不能直接返回 [0,0]
- 可以按照任何順序返回答案
Describe
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]
Output: 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 <= 103-109 <= nums[i] <= 109-109 <= target <= 109- Only one valid answer exists.
java
//version 1 兩次hash table ； 可讀性相對(duì)高
public static 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);
}
for (int i = 0; i < nums.length; i++) {
int searchWithMap = target - nums[i];
if (map.containsKey(searchWithMap) && i != map.get(searchWithMap)) {
return new int[]{i, map.get(searchWithMap)};
}
}
return null;
}
//version 2 單次hash table媒役； 可讀性相對(duì)低
public static int[] twoSumOneHashTable(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
python
def two_sum(nums, target):
ele_map = {}
result = [-1, -1]
for index, ele in enumerate(nums):
ele_map[ele] = index
for index, ele in enumerate(nums):
if target - ele in ele_map and index != ele_map.get(target - ele):
result[0] = index
result[1] = ele_map.get(target - ele)
return result
