视频来自 ： 爱学习的饲养员。

爱学习的饲养员的个人空间_哔哩哔哩_bilibilihttps://space.bilibili.com/31337561/channel/seriesdetail?sid=389852一、双指针

用多个指针解决问题。也有三指针、四指针。

普通双指针：两个指针往同一个方向移动，(有时候是不同方向。这里特指复杂度是O(n^2)的暴力法)；

对撞双指针：两个指针面对面移动；

快慢双指针：慢指针+快指针；

----------

例题：a=[1,4,5,7,9]，两个数相加=12。

普通2指针：两个for循环

对撞双指针：先排序，左小右大。i指向头，j指向尾。求和sum，若sum大于12，那么最右边的j左移，（sum缩小了）；若sum小于12，那么最左边的i右移，（sum扩大了）；直到sum等于12。

--------

快慢双指针，判断链表是否是环形的。

二、二分查找

针对有序数组。（左小右大）。查target值是否存在于数组里，从子数组的中间值，如果该值小于target，则取右子数组，下次在右子数组里找target；如果该值大于target，则取左子数组，下次在左子数组里找target。

O(log2(N)).

----------------

三、滑动窗口

目的：减少while循环

例：a=[1,4,2,3,4,5,6]，数组连续3个数，取最大的和。

直接算也能做。

观察：当计算了1+4+2以后，再计算4+2+3，那么4+2就重复计算了。

优化：当计算过一组数的sum以后，要计算下一组的sum，只需要减去 [出去的数]，加上

[进来的数]，就达到减少重复计算的目的了。将固定长度的连续数组比作滑动窗口，窗口越长，减少重复运算的效果就越明显。

解决数组中定长问题。

四、递归

递归的定义：函数直接或间接地调用自己。

递归的4要素

//递归在使用的过程中，会保存很多中间变量，占用了额外的资源。程序员写起来容易，但是更推荐迭代。

从实现角度讲，迭代是在局部内存进行重复计算，递归需要展开栈空间进行每一步的函数现场存储和结果存储。迭代没有这个展开的开销。（知乎：Larry Sean）

五、分治法

大问题分成小问题，然后小问题求解，最后合并。

用到了递归，自己调用自己。

-----以归并排序为例:a=[7,8,4,1,6,5,2,3]，排序

把数组a对半分；        [7,8,4,1],   [6,5,2,3]

                                   [7,8],[4,1],[6,5],[2,3]

分成两两一组，进行两两排序。

                                [7,8], [1,4],     [5,6], [2,3]

相邻合并 [1,4,7,8]   ,[2,3,5,6]

                [1,2,3,4,5,6,7,8]

有更清楚的讲解

图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 (cnblogs.com)https://www.cnblogs.com/chengxiao/p/6194356.html

六、

七、

八、

九、