给定一个整形数组和一个整数n，从数组中找到两个数的索引使这两个数之和等于n，以数组的形式返回这两个数的索引。(假设数组中只存在一组这样的数)
例如：
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
循环遍历
首先映入脑海的解决方案，逐步遍历数组中的每个元素，查找是否存在。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for(int i=0; i< nums.length; i++) {
int first = nums[i];
result[0] = i;
int second = target - first;
for(int j=i+1; j<nums.length; j++){
if(second == nums[j]){
result[1] = j;
break;
}
}
if(result[1] != 0){
break;
}
}
return result;
}
}
|
代码中涉及两个for循环，注意到第二个for循环其实是在剩余的数组元素中查找是否存在目标数字second，则可以想到如果数组是有序的，则可以使用二分查找来提高效率。
则对上面思路的一种改进是假如数组是无序的，则先使用快排对其进行排序，然后遍历数组中的每一个元素，使用二分查找再数组中查看是否存在second，存在则找到second对应的索引i。
使用hashmap进行改进
从上面的思路中可以看出第一个for循环是不可少的，第二个for循环其实是充当一个查找的功能，则可以使用二分查找进行改进，但是是否可以借助别的数据结构使其能够更快的找到second的索引i。
目的是能够快速的找到second对应的索引i，则second和i是一一对应的关系，存放这种关系的数据结构很容易想到HashMap，也就是将数组中的元素和索引放入map中，元素作为key，这样直接去map中get key对应的value就ok了。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++){
if(null == numsMap.get(nums[i])){
numsMap.put(nums[i], i);
}
}
int[] result = new int[2];
for(int i=0; i<nums.length; i++){
Integer j = numsMap.get(target - nums[i]);
if(null != j){
if(j < i){
result[0] = j;
result[1] = i;
}else if(j > i){
result[0] = i;
result[1] = j;
}
}
}
return result;
}
}
|
对于上述代码依然可以精简，但只是精简代码行数而已，并不能提高时间复杂度。
精简的方法是在第一遍遍历数组的时候就对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
| public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
int[] result = new int[2];
for(int i=0; i<nums.length; i++){
int second = target - nums[i];
if(numsMap.containsKey(second)){
Integer j = numsMap.get(second);
if(j < i){
result[0] = j;
result[1] = i;
}else if(j > i){
result[0] = i;
result[1] = j;
}
break;
}
if(null == numsMap.get(nums[i])){
numsMap.put(nums[i], i);
}
}
return result;
}
}
|
总结
遇到此题首先想到的是使用循环遍历找到两个数的索引，其次在遍历的过程中发现第二个for循环其实是遍历查找的功能，说到查找的优化很容易想到的就是二分查找，然后查看是否可以用二分查找，如果不可以则去创造条件使其满足二分查找的条件。
再者在数组中查找一个数是否在数组中，使用hash映射查找只需O(1)的时间复杂度，则构建一个HashMap，使用hash映射查找优化二分查找。
注意，并不是在任何情况下构建HashMap进行查找都会比二分查找要快。因为构建HashMap需要O(n)的时间复杂度去遍历数组。
wechat