leetcode练习-简单-第一题-两数之和

说在前面

自己本来就是个彩笔再加上长时间写CRUD,数据结构方面早早的就忘光了,心血来潮,回顾一下数据结构和算法,先从简单的题目开始

问题

提供一个整数数组,一个整数的结果值,如果数组内部任意两个整数的和等于结果值,返回含有这两个数字的坐标的数组
eg:输入值[1,2,3,4,5],8 返回值 [2,4]

解决方案

直接遍历

解决思路

看到问题,想到的最简单也是最粗爆的方案就是遍历,两个遍历进行嵌套,找到结果就返回,如果遍历结束就返回null

代码

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
for (int num = 0; num < nums.length-1; num++) {
for (int a=1;num+a<nums.length;a++){
if(nums[num]+nums[num+a]==target) {
int[] ret={num,num+a};
return ret;
}
}
}
return null;

方案分析

时间复杂度:由于两个循环嵌套,时间复杂度是O(n²)
空间复杂度:并不需要额外的空间,复杂度是O(1)

哈希查找

遍历法的时间主要用在了遍历查找差值上,如果可以加快查询速度就降低了时间复杂度
哈希表的设计目的就是使用空间来换取时间,由于每次查询的是hash值,时间上可以认为是近似恒定的,所以每次查询的时间复杂度可以任务是O(1)
解决方案就是进行两次循环,第一次用于将数组内的数据放入hashmap,第二次循环查询有没有结果值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
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 null;
}

方案分析

时间复杂度:两次循环,时间复杂度是O(n)
空间复杂度:需要一个新的哈希表,复杂度是O(n)

一次哈希遍历

在第二种方案的基础上进行优化,每往哈希表里添加一个数字以后,检查有没有所对应的结果值,如果存在则直接返回结果

代码

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return null;
}

方案分析

时间复杂度:两次循环,时间复杂度是O(n)
空间复杂度:需要一个新的哈希表,复杂度是O(n)