两数之和


题目描述

给定一个整数数组 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)
两数之和 | 题解


文章标题:两数之和
文章作者:cylong
文章链接:http://www.cylong.com/blog/2019/11/06/two-sum/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)