本文共 2992 字，大约阅读时间需要 9 分钟。
好久都没有写文章啦，React系列的文章还差一篇，但是感觉讲+写已经很腻了，所以先放一放，换一下口味吧！
今天我们来看看算法在实际问题中的应用，还是很有意思的哇~~~
思想：对撞指针的意思就是有两个指针，一个从开头，一个从结尾，两个指针分别++，--直到碰撞。
这个思想可以解决什么问题呢？
题目：leedcode 167
给定一个从小到大有序的数组，从数组里找到两个数字可以等于target,并返回索引。
即：
Input: numbers = [2,7,11,15], target = 9 Output: [1,2]
分析：这道题可以直接用查找的方法，一层层循环去找。但是这样做时间复杂度为O(n2),而且完全没有利用到我们这个数组有序的特性。
更好的解法是：两个指针，分别从两边去找，相加>target，右边指针--前移，如果<target,左边指针++前移，一直到这两个指针碰撞，如果找到结果可以返回相应的索引。
代码实现：
var twoSum = function(nums, target) { var left = 0; var right = nums.length - 1 ; // 对撞的循环条件：左边指针小于右边指针 while(left < right ) { if(nums[left] + nums[right] === target) { return [left, right] } else if(nums[left] + nums[right] > target ) { right--; } else { left++; } } }; 思想：
有两个指针构成一个区间，通过往同一个方向不停的移动，来找到满足条件的区间。
滑动窗口关键的是想想初始时候，两个指针在哪，在滑动的时候，两个指针基于什么条件移动，移动后的位置又在哪里。
下面来分析一个题目来看看如何用这个思想。
题目：leedcode 209
给定一个整形数组和一个数字s,找到数组中最短的一个连续子数组，使得连续子数组的数组和sum >= s,返回这个最短的连续子数组的长度值。
即：
Input: s = 7, nums = [2,3,1,2,4,3] Output: 2
分析：这里依旧可以采取暴力解法，找出所有的子数组，再分别相加求解。但是这里介绍更好的解法。
这里可以看到由于需要找连续的子数组，所以依旧可以设置两个指针，往同一方向移动。
如果两个指针中间的值加起来>sum的时候，记录此时数组的长度，接着左指针移动，减小sum的值 ；
如果< sum的话，右指针移动扩大范围。
最后返回最短的长度值。
代码实现：
/** * @param {number} s * @param {number[]} nums * @return {number} */var minSubArrayLen = function(s, nums) { var left = 0; var right = -1; // right 的起始位置很重要，这里选择-1 [left, right]这个区间刚开始是没有值的 var tmpSum = 0; var minLength; // 循环停止的条件是左指针小于长度 while (left < nums.length - 1) { if(tmpSum < s) { // 这里要注意边界的处理，当右指针移动到最后一个元素的时候结束 if(right >= nums.length -1) { return minLength || 0; } right ++; // 这里tmpSum的计算也很巧妙，直接用累加的方式，节省计算量 tmpSum = tmpSum + nums[right] } else { var tmp = right - left + 1; if(minLength) { if(tmp < minLength) { minLength = tmp; } } else { minLength = tmp; } // 左边指针移动减少sum的值 tmpSum = tmpSum - nums[left]; left ++; } } if(!minLength) { return 0; } return minLength;}; 这里先介绍两种数据结构 ，不了解的同学先自行学习一下，其实很简单，Set类型就是只有key的一种数据结构，而Map类型有key，value。
而在JS中，Object类型基本跟Map类型的一样使用，但是还是有些不同的，也可以在这边里了解不同。
接下来通过具体的例子来看看如何使用它们。
题目：leedcode 1
这个问题跟开头的问题一样，给定一个数组numbers，从数组里找到两个数字可以等于target,并返回索引。
即：
Input: numbers = [2,7,11,15], target = 9 Output: [1,2]
分析：
除了暴力的解法，我们还可以用刚刚介绍的对撞指针的思路，先给它排序，在使用对撞指针，但是我们这里由于要返回索引，所以还要记录排序前的索引。其实这个思路也是有点麻烦的。
这里在介绍巧妙查找表的思路：
我们可以先定义一个Object类型的数据结构obj，它的key为target - numbers[i]（比如数组第一项为2），value为索引。然后每次都看看obj[numbers[i]] 是否存在，如果存在，那我们就找到了这样的一组数据，返回当前索引以及obj[numbers[i]]。
代码实现：
/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function(nums, target) { var obj = {}; for(var i=0; i< nums.length;i++) { const item = nums[i]; if(obj[item] >= 0) { return [obj[item], i] } else { obj[target - item] = i; } }}; 面试中常考的数组去重的问题，也可以借助Object的查找思路，可以自行练习。
因为在公司有后台处理数据，所以总觉得算法跟前端没有太大的关系，在看React源码的时候，里面使用了深度查找的思想。所以我觉得学好算法对我们还是很重要的。后面接着~
本文对你有帮助的话，点个赞鼓励一下作者呗 (੭ु≧▽≦)੭ु
原文
转载地址：http://npwii.baihongyu.com/