坚持就是胜利，开始刷题之旅
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
1
2
3
4
5
| 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
|
思路
读懂这道题后的第一反应就是暴力向后搜索。但是这样的复杂度是O(n^2),肯定没有这么简单。只能通过空间来换时间，那么有什么查询方式是O(1)呢？第一反应是散列查找，也就是哈希查找。在java中。有HashMap类可以实现这个需求，那么代码可以是这个样子
代码
解法一
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
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//初始化一个int对应int的hashmap
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
//初始化结果数组
int[] res = new int[2];
//将题目给定的数组放入hashmap中
for (int i = 0; i < nums.length; i++) {
m.put(nums[i], i);
}
//开始搜索
for (int i = 0; i < nums.length; i++) {
//搜索值等于和减去当前值
int t = target - nums[i];
//在hashmap中搜索并且保证存在而且不等于当前值
if (m.containsKey(t) && m.get(t) != i) {
//对结果进行赋值，搜索到所以退出搜索
res[0] = i;
res[1] = m.get(t);
break;
}
}
return res;
}
};
|
提交上述代码，会发现内存消耗很大，时间也只是9ms超过了80%的人。一定有更优的解法。百度后发现可以将两个操作合二为一。上述解法先是将数组放入hashmap中，然后再进行查找。可不可以边放边找呢？先全部放入就是拿到前面的数去找后面的数。边放边找就是拿着后面的数去找前面的数。仔细想想，确实是这个道理。那么试试？？
解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for (int i = 0; i < nums.length; i++) {
if(m.containsKey(target - nums[i])){
res[1]=i;
res[0]=m.get(target - nums[i]);
break;
}
m.put(nums[i], i);
}
return res;
}
}
|
上述方法快了1ms,内存消耗也少了。