《每天三分钟-算法修行》两数求和之解与应用
一、前言[*]大家好，我是小诚，终于，我还是将“魔爪”伸到了算法，在编写《算法日记》之前，我也考虑过许多问题，现在网上关于leetcode算法的案例这么多，我再重新"造轮子"有没有必要。
[*]最后和圈子中的朋友聊了聊(有能够聊天的朋友还是不错的)，其实这些担心都是多余的，在编写的过程中，我自己不仅在算法和文笔上有了进步，还可能会帮助到一些"有缘"看到文章的朋友，这样即使重复"造轮子"又如何。
[*] 《算法日记》系列特点：更加注重结合实际情况，将算法和实际开发中问题或面试举例相结合，让学习算法更有意义。(不信继续往下看！)
二、两数求和
2.1、算法题目
给定一个整数数组 nums 和一个整数目标值 target，请你 在该数组中找出和为目标值 target的那个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。返回答案顺序任意。
示例：
示例一：
输入：nums = , target = 9
输出：
解释：因为 nums + nums == 9 ，返回 。
示例二：
输入：nums = , target = 6
输出：
示例三：
输入：nums = , target = 6
输出：
2.2、分析题目
题目的意思很清晰，输入一个目标值，然后在数组中找到两个元素值之和为这个目标值，并返回它们这两个元素的数组下标，需要注意的题目要求中提到：数组中同一个元素在答案中不能重复出现，这个是什么含义呢?
其实看上面的示例三就知道，输入目标值为6，但是数组中元素都为3，这时候返回的结果必须为【0，1】或者【1，0】，而不能是【0，0】或者【1，1】即不能返回下标都是一样的结果。
2.3、解题方案一
一、解题思路
梳理完题目的含义后，相信很多人脑海里已经浮现了一个解题方案，那就是：使用for循环 + if条件判断来找出和目标值一致的两个元素，下面来看看如何实现：
/**
* 方案一：双重for循环
* @param nums
* @param target
* @return
*/
public static int[] twoSum2(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = 1; j < nums.length; j++) {
// 比较查询找到符合目标值的两个元素
if (nums + nums == target) {
return new int[]{i, j};
}
}
}
return null;
}
二、解题方案评审
如果是在面试中，使用上面的题目解决这个问题，面试官最多给你打60分，为什么? 我们需要先看看这个算法的时间复杂度是多少！(不知道时间复杂度和算法指标的一定要先看我之前发的一篇文章：【算法基础知识讲解】小白都也能看得懂)
从算法知识讲解的文章中，我们可以知道 时间复杂度主要是跟：对运行时间有消耗的基本操作的执行次数成正比。 再继续看上面的程序，我们会发现，对运行时间消耗的基本操作实际上就是if条件判断的语句。
随着问题规模n的增大，它的判断次数也会增多，使用问题规模函数来表达的话就是：f(n) = n^2^，既它的时间复杂度为O(n^2^)， 那我们有没有更好的方式来进行优化呢? 答案是有滴，请继续往下看！
2.4、解题方案一优化
一、优化思路
上面的方案我们使用的是暴力破解的方式，最差情况是两个循环到最后一个元素才能够找到符合题目的答案，既然我们知道了运行时间都花费在if条件的比较逻辑上，是否能够通过减少比较逻辑达到减少运行时间呢，没错，确实存在可以优化的方法，下面先来看看优化后的代码吧。
二、优化后的代码
/**
* 方案一优化：选择排序法
*
* @param nums
* @param target
* @return
*/
public static int[] twoSum2(int[] nums, int target) {
// length - 1的目的：每轮都会和集合其他元素比较筛选出一个最大/小值
// 意味着最后一个元素已经和之前所有的元素比较过了，无需再循环一次
for (int i = 0; i < nums.length - 1; i++) {
// j = i + 1表示：比较元素跳过与自身的比较，较少比较次数
for (int j = i + 1; j < nums.length; j++) {
if (nums + nums == target) {
return new int[]{i, j};
}
}
}
return null;
}
特点： 对比第一种方案和优化后的方案，你会发现它们的区别主要是在第二层的 for (int j = i + 1; j < nums.length; j++) 中，这个的含义主要是：每轮都将最外层之前比较过的元素筛选出去，不再进行重复比较，具体可以通过下面的案例来清楚认识到。
比如要循环一个数组【1、2、11、7】找出和为9的两个元素下标，我们会进行如下的操作：
1、第一轮循环外层会使用【1】和内层中【2,、11、7】做运算，但没找有符合条件的两个元素，继续循环。
2、第二次外层循环拿2和内层中的【11,7】做元素，得到符合条件的结果，如果没有，则以此类推继续进行第三轮、第四轮…的操作。
通过这个操作，我们会发现，每次循环都会跳过之前已经比较过的元素(因为已经确定它们是不满足条件的)，即内层循环都是从i+1开始比较的，这个就减少了不必要的比较，节省了运算时间，下面我们来推到下它的时间复杂度吧。
三、推导优化后的代码的时间复杂度
通过上面的案例步骤我们会发现，随着每次循环的进行(即i++)，内层循环的次数(即j<nums.length)会逐渐减小(因为j=i+1)，呈现如下规律：n-1次、n-2次，n-3次...等等，你是不是已经发现，内层循环的比较次数就是一个等差数列，公差为1(注：如果对等差数列不是很熟悉的同学，可以直接百度下，几分钟就能掌握)
通过等差数列的求和方式：Sn=n*a1+n(n-1)d/2，我们可以得到耗费运行时间的函数f(n) = n*a1+n(n-1)d/2，再根据大O记法的推断，可以得出优化后的方法时间复杂度为O(n^2^)。 不知道大O记法的请看：算法基础
四、这个优化方式有何意义
上面优化后的方案后算法推算出来的时间复杂度还是O(n^2^)，肯定有同学会疑问，既然最终的时间复杂度和优化之前一样，这个方案有啥作用？诚然，这个方法如果当输入规模即n无限扩大的时候，和没有优化之前效率相差不大，但是在面试的时候，如果你能够给面试官讲解出来，面试官会在60分的基础给你加10分，为什么？
这10分是对你遇到问题肯钻研、并且能够找到一些提高效率的方式的一个肯定，面试官看重的不仅是你当前的一个能力，还要考量的是你的一个学习力、成长力。
2.5、解题方案二
既然使用上面的优化方式不能解决我们的问题，我们就需要另辟蹊径。相信开发的同学或多或少都听说过“使用时间换空间和使用空间换时间”这两个概念，那么在这个题目中能否采用这个方式呢？没错，解决这个问题采用空间换取时间的方式会更好，下面就来看看具体的实现方式吧。
public static int[] twoSum(int[] nums, int target) {
// 使用HashTable存储数组的值和下标
Hashtable<Integer, Integer> keyMap = new Hashtable<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
// 每次循环时判断是否在hashtable中存在与当前循环的值相加等于target，如果有则返回
if (keyMap.containsKey(target - nums)) {
return new int[]{keyMap.get(target - nums), i};
}
// 没有找到符合条件的值则将元素值和下标存储起来
keyMap.put(nums, i);
}
return null;
}
通过上面的代码，你会发现问题规模函数f(n) = n(即只存在一层循环，随着n的增到，循环次数也会增大)，通过大O记法可推断出时间复杂度为O(n)，上面的算法中引入了Hashtable，目的就是将数组中的值存储起来，减少内层循环，这个就是空间换时间的一种方式，下面通过具体的图片来看看时间复杂度O(n)和O(n^2^有多大的区别。
2.6、实际业务中的运用
在业务中，使用多层for查找符合条件的数据是很常见的业务，比如对某些数据进行排序，我们会使用到选择排序法、冒泡排序法等，它们都是通过for去解决排序问题。
以控件换时间的方案，在开发中也非常常见，比如为了提高数据的检索速度，我们会给适当的字段创建对应的索引，以便快速定位到需要的数据。还有各种nosql数据库如redis，本质上也是通过控件换时间的方式来提高效率。
三、写在最后
通过上面三种不同解决方案，你会发现，寻找最优方式对大多数人来说是一个循序渐进的过程，很多人刚开始并不会立马就想到使用空间换取时间的方案来解决这个问题，就像你刚开始学习算法的时候，可能也觉得很难，又要编程、还可能涉及到数学知识。
你可以有退却之心，但更要有试一试的勇气，算法看上去是很难，但是，你可以先开始第一步，尝试着了解算法的知识，尝试着去解决简单的算法问题，一步步坚持下来，你会发现，算法也没有这么难，数学也没有这么难。
请记住！一个人可以走得很快，但是一群人才能走得更远！ 欢迎加入技术人的圈子【技术圈子】，共享资源，共同成长！
页:
[1]