题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题解
使用哈希表将会使问题特别简单，首先，我们将使用一次遍历将数组中的元素加入到Map中，key是当前元素的值，value是当前元素的索引。接下来，我们进行第二次遍历，第二次遍历我们将查找当前元素的目标元素（target−nums[i]）是否在Map中，如果在，即找到目标值，返回两个元素的索引。注意一点的是，目标元素不能是当前元素！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[0];
}
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 complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[]{i, map.get(complement)};
}
}
return new int[0];
}
|
实际上，我们把上面的两步合成一步，只用一次遍历即可完成，当遍历到第i个值后，我们把此元素的需要的目标值保存到Map中，后续遍历，找到目标的值，即完成遍历。
1
2
3
4
5
6
7
8
9
10
| public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
}
map.put(target - nums[i], i);
}
return new int[]{-1, -1};
}
|
来源
两数之和 | 力扣（LeetCode）
两数之和 | 题解（LeetCode）
