既然决定开始写博客，那么就先从最简单的开始写起。鉴于上次失败的面试经历，也为了补全巩固自己的数据结构和算法等的知识点和动手能力，就拿leetcode上的题目来分析一下吧。
Problem 1.Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element >>twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
题目大概的意思是给定一个整数和一个数组，求解数组中两个数值和等于该整数的下标。
思路
先来分析下题目，题目中假设每个输入都会有确定的一个解，而返回的数组中两个下标不能一样，也就是不能取同一个数两次，对于返回结果也没有规定两个下标之间的顺序，并且数组并没有说有序。
对于这类搜索类的问题，不假思索而又最简单的思路就是暴力搜索。
暴力搜索
public int[] twoSum(int[] nums, int target) {
for(int i = 0 ; i < nums.length ; i ++){
for(int j = i + 1 ; j < nums.length ; j ++){
if(nums[i] + nums[j] == target){
return new int[]{i, j};
}
}
}
return null;
}
时间复杂度：O(n^2)
空间复杂度：O(1)
leetcode上运行耗时大概在39 ms左右
问题
1. 在n较大时候会导致时间复杂度过高
对于以上的解法估计很多人都会发出啧啧啧的感叹声，写了这么久代码才会这么简单的解法，小学生都会写啦，九年义务教育就教你这个？（没错，九年义务教育就教这个）其实个人觉得不管白猫黑猫，抓到老鼠就是好猫。言归正传，问题正如以上所说对于这种时间复杂度为O(n^2)的解法，在n比较大的情况会导致耗时过高。
排序后搜索
既然暴力搜索不能满足我们的需求，自然我们想到对数组进行排序，毕竟排序后的数组在搜索问题上比较有优势（可利用二分查找）。题目返回的结果是数组的下标，如果排序的话就会打乱原数组的顺序，此时我们可以维护排序后的数组到原数组下标的映射关系，在匹配到对应元素值之后返回原数组的下标。理所当然这种下标的映射关系会带来额外的空间开销。
这里排序后的映射关系到原数组的映射关系的维护的办法有很多，我们既可以用面向对象的思想将数组的原下标以及数值封装到同一个对象里，然后以原数组的顺序建立起对象数组，最后对对象数组排序，而搜索过程就在排序后的对象数组中进行，最后得到两个对象的下标返回。
还有一种直接维护一个hashmap对应关系，key值等于排序后数值在数组的位置下标 ，value则是该数值在原数组的下标， 在排序过程中每发生一次元素位置的变动就相应修改hashmap中的key-value值（可能对应key-value的新增，修改和删除），最后排序过后就是以新下标为key,原下标为value的hashmap,最后对数组搜索并且从hashmap中拿到结果返回。
无论哪种方法都会带来O(n)的空间复杂度的增加,好处就是将时间复杂度降低为O(nlogn)。
先实现第一种将对象下标封装在数组的做法，其实也就是将这种映射关系内化到新对象数组中，跟第二种将映射关系独立出来到hashmap中的做法没有本质的区别。
定义封装的对象
/**
* 数字实体
*/
public static final class Num{
//数组原下标
private int originIndex;
//值
private int value;
public int getOriginIndex() {
return originIndex;
}
public void setOriginIndex(int originIndex) {
this.originIndex = originIndex;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Num(int originIndex, int value) {
this.originIndex = originIndex;
this.value = value;
}
@Override
public String toString() {
return "Num{" +
"originIndex=" + originIndex +
", value=" + value +
'}';
}
}
快速排序
/**
* 快速排序
* @param list
*/
public static void quickSortWithNum(Num[] list , int start , int end){
if(start >= end){
return;
}
//选取标志元素
Num index = list[start];
int i = start, j = end;
while(i < j){
while(i < j && list[j].getValue() >= index.getValue()){
j--;
}
if(i >= j){
break;
}
list[i] = list[j];
while(i < j && list[i].getValue() <= index.getValue()){
i++;
}
if(i >= j){
break;
}
list[j] = list[i];
}
list[i] = index;
quickSortWithNum(list , start , i - 1);
quickSortWithNum(list , i + 1 , end);
}
对对象数组排序并且返回结果
/**
* 排序过后搜索
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums, int target) {
Num[] list = new Num[nums.length];
for(int i = 0 ; i < nums.length ; i ++){
list[i] = new Num(i , nums[i]);
}
//快速排序
.quickSortWithNum(list , 0 , list.length - 1);
int i = 0 , j = list.length - 1;
while(i < j && list[i].getValue() + list[j].getValue() != target){
int x = list[i].getValue() + list[j].getValue();
if(x > target){
j--;
}else if(x < target){
i++;
}
}
return new int[]{list[i].getOriginIndex() , list[j].getOriginIndex()};
}
时间复杂度：O(nlogn)
空间复杂度：O(n)
leetcode上运行耗时大概在40 ms - 80 ms左右
问题
1. 创建对象的时空消耗较高令降低时间复杂度的优势不在
运行耗时比上面的暴力搜索还要略高，为什么？因为创建对象也需要耗时，虚拟机需要一系列的加载类，验证，解析，初始化类的操作，这样一对比暴力搜索并没有特别大的优势。
这下我们再来反观题目，题目的意思是搜索，对于搜索的过程其实是只需要找到满足条件的结果就返回，而上面我们则对数组进行了排序，排序过程是一个从无序到全局有序的过程，我们并不需要这样全局有序的结果去得到我们的值，况且排序过程中的创建对象的开销令这种降低时间复杂度的优势不复存在。在思考过程中如果发现思路走进了死胡同，那么就得重新调整思考方向，重新审视题目本身。其实对于这种搜索类的题目，我们大概有两个方向去思考，第一是如前面所说的建立全局有序的序列，再在序列上进行操作，第二我们可以借助hashmap这种键值对的映射关系去进行搜索。
其实我们只需要在遍历数组的时候，先判断此时hashmap中是否存在target-当前元素值的值存在，存在则取出来并返回就可以了（注意）。不存在的话以当前元素的值为key,下标为value存入hashmap中即可。
借助hashmap构造的值和下标的映射
/**
* 借助hashmap构造的值和下标的映射
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums , int target){
HashMap<Integer , Integer> hashMap = new HashMap<>(nums.length);
for(int i = 0 ; i < nums.length ; i ++ ){
int j = target - nums[i];
if(hashMap.containsKey(j)){
return new int[]{i , hashMap.get(j)};
}
hashMap.put(nums[i] , i);
}
throw new IllegalArgumentException("error input");
}
时间复杂度：O(n)
空间复杂度：O(n)
leetcode上运行耗时大概在10 ms以内
问题
1. 引入了hashmap这种数据结构，但是我们要考虑到hashmap中存在的hash冲突的情况，对于hash冲突最极端的情况就退化为线性搜索或者二叉树的搜索了（线性搜索或二叉树搜索是由jdk8的hashmap实现决定的，其hashmap采用拉链法解决冲突，并且在单个slot中链表长度超过8的时候会转换成红黑树，所以搜索的时间复杂度会在O(logn) 到 O(n)之间）。所以我们要谨慎选择对应的hash函数。
其实上面的解法是leetcode上官方的解法，在时间和空间效率上都非常高，那么我们还有没有别的解法不借助hashmap来实现呢？我们来利用下数组？先来看看数组有什么参数，一个是数组的长度，下标，数组内对应下标的值，假如我们将搜索过程限制在对数组内的值的搜索，问题又会退化到建立hashmap或者排序上。那么我们假如将原始数组的值的搜索遍历转化为对新数组的下标的计算会如何？
我们先建立一个足够大的数组A，然后遍历原始数组，先将原始数组的值映射到新数组A的下标中，而原始数组的下标则映射到新数组A对应下标的值中来。这样我们就顺利规避了hashmap中存在的hash冲突的极端情况，但是又引入了新的问题，这个足够大的数组显然需要的长度是数组中元素值的最大值，当最坏情况数组中元素数量很少，但值很大的时候就会又大量的空间被浪费。相反，当原始数组中值较多而值比较“紧密”的时候，空间利用率就比较高。其实现的遍历过程跟以上leetcode的遍历过程类型。
借助数组的长度和下标的实现
/**
* 借助数组实现
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums , int target){
int[] existNums = new int[Integer.MAX_VALUE];
for(int i = 0 ; i < nums.length ; i ++){
int j = target - nums[i];
if(existNums[j] != 0){
return new int[]{existNums[j] , i};
}
existNums[nums[i]] = i;
}
throw new IllegalArgumentException("error input");
}
时间复杂度：O(n)
空间复杂度：O(k)(k是数组中数值最大的那个数)
leetcode测试无法通过
问题
1.算法依赖于数组中数据的值的大小，在数组中数量较小而值(k)比较大的情况下大量空间被浪费
2.应用范围小
其实以上借助数组长度和下标的实现思想上跟leetcode上的借助hashmap类似，hashmap
中是将原数组中的值作为key,而原始下标作为value,而以上做法则是将原数组中的值作为新数组的长度，而原始下标作为新数组中的值。hashmap中的原数组的映射关系是作为一个个实体被添加到hashmap中，可以动态添加，空间占用小可扩展。而上面的数组做法则是将映射关系变换到数组的长度和值中来，而盛放这种映射关系最致命的地方在于这个容器的长度是由原始数组的值所决定的，因此适用范围小。
总结
观察以上算法都会发现，算法的本质上还是在追求时间和空间上的平衡，鱼与熊掌可得兼情况非常少。
后记
这篇文章断断续续写了一天，也是第一次写博客，写得也比较乱，比较啰嗦，就当是给自己的学习过程做记录吧。以后会争取保持周更两篇，不一定都是数据结构算法和leetcode的题，还包括一些框架中间件技术上个人的一些学习过程和体会，希望以此加深自己的理解。
网友评论