数据结构算法之leetcode Two Sum

给定一个整形数组和一个整数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)的时间复杂度去遍历数组。

您的肯定,是我装逼的最大的动力!