题目地址(1. 两数之和)
https://leetcode-cn.com/problems/two-sum/
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
|
前置知识
公司
思路
此题作为LeetCode的第一题，最容易想到的就是使用暴力的方法进行枚举，O(N^2)的复杂度就可以将最终结果解出来，但是这样的效率是非常低的，显然不是题目本身的意图。这里可以使用哈希表的解法，每次将nums中元素添加到哈希表中时，使用containsKey()进行判断，判断是否有相加为target的元素已经存在哈希表中，如果存在直接返回对应的下标，如果没有，则将当前元素以num[i]为key，索引为value存入到哈希表中。
关键点
- 哈希表的使用，containsKey()的使用。可以直接返回新建的数组，这样代码更加简洁高效。
代码
Java Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] index=new int[2];
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return index;
}
}
|
复杂度分析
令 n 为数组长度。