双指针
移动零
移动零
这里的解题思想是数组的划分，数组分块，用到双指针算法，此处指针用数组下标来表示
这里的数组分块，总的分为两大部分，处理过和待处理部分，按题目要求，数组前侧为处理过部分，后侧为待处理，而而处理部分内部也有两个分区，非0区和0区
有两个指针 一个是cur 当前位置， 从做数组的整体遍历的，还有一个是dest 表示已处理区间内，非0 元素的最后一个位置
所以有了三个分区 [0,dest] [dest + 1 , cur -1] [cur，n-1 ]，三区，分别为非 0 区 0 区 待处理区
只要这两个指针在从左往右遍历，一直保持上面区间的性质，就是双指针的本质
下面举一个例子来理解
以上是代码
拓展
这里双指针的算法其实快速排序中最核心的部分
复写零
复写零
本题先是由简到难，先理解异地的复写操作，即创建一个等长的数组，完成复写，异地的操作的分隔开的，所以相对好理解cur在原数组，而dest在复写数组中，根据判断cur所在数的类型，来决定是拷贝非0值还是连续赋值两个0，直到dest到达arr.size()的位置
但是本题是要求在本地上完成，我们试着用异地的方法，从前往后复写，当遇到0的时候我们会发现，多复写0会覆盖后面待复写的数据，导致算法失败！所以从前往后是不行的！
从前往后不行，我们试试从后往前！从后往前我们找到最后一个被复写的数据，开始后往前复写，遇到非0元素直接拷贝，再同时--，遇到0时，再dest和dest-1的位置赋0，因为cur会在dest前面或相等，所以dest-1的数据是已经被处理过的，被覆盖也没关系，这样就可以解这个算法
只是还有一个关键的问题，我们要如何找到最后一个复写数呢？
同样可以使用双指针算法来解决，cur指针来判断数据类型，dest来做移位，根据cur数据的不同，dest+1或+2，只移动不赋值，判断dest是否到结尾，最后再移动cur！这样不仅能找到最后一个复写值，还可以把dest移动到数组末尾直接开始后往前的遍历复写！
注意：[1 0 2 3 0 4 ]有一种dest越界的问题，最后一个复写数位0 ，dest最后的位置不是arr.size()-1,而是在arr.size()的位置，之后开始复写会在此处赋值0，这样是在做越界操作，leetcode会报错，所以要特殊处理一下！
时间复杂度为O(n)！
快乐数
快乐数
快乐数： 一个正整数每次被自己每位数平方和替换，重复这个过程知道这个数为1的数为快乐数
算法原理：
这个问题会有两种情况，一个结果是一直是1，一个是无限循环但永不为1
上面的两个例子我们可以知道，操作的结果都会是进入一个环，一直在其中做循环！这个环的结构非常眼熟，就是判断链表是否有环！
而这里不用判断是否有环，而是要判断这个抽象链表内部的值（是否为1！）
而判断链表是否有环，是用快慢双指针解决的！
1、定义快慢指针
2、慢指针每次向后移动一步，快指针每次向后移动两步
3、判断相遇时候的值
但这里要如如何实现快慢双指针呢？之前链表还可以定义两个链表节点指针！但这里并没要数据结构，要如何实现？
不要局限思维！之前的两道题也是双指针算法解决，而两题的数据结构为数组连续结构，这两题是以下标作为双指针，而这里是将两个整数抽象为两个双指针，用来记录两个指针移动时候在抽象链表该节点的数值
所以双指针是一种思想，不要被指针而束缚了思维！
这题简单是告诉你数据必定能成环，还有种可能数据是不会成环！
拓展
为什么数据变化一定会成环！
鸽巢原理（抽屉原理）
n个巢穴 ， n+1个鸽子 ---> 至少有一个巢，里面的鸽子数大于1这道题整数的最大值为int整型的最大值，2^31^ 约等于 2.1 X 10^9^ 那么找个比这个数大一点的数！10个9
9999999999，那么10个9经过题目操作后的数，int数据经过题目操作的数一定小于这个数！
为810，所以题目数据的变化范围是在[1 ，810]，一共810个数据，这个时候我们就有巢穴，1~810就是我们的巢穴，随机的整型数据X经过811次题目操作，即使运气好，把所有巢穴都填满了，但是第811次的时候，数据必然会在1 ~ 810 之间出现，所有会有重复，形成环！
代码实现：
盛水最多的容器
盛水最多的容器
题目讲解！
本题height数组存放的是从0 ~ n-1线的高度，而题目要求获得桶的最大体积！桶的体积x轴容易知道！i~Min~ - i~Max~,而桶高有木桶效应，选两边中比较矮的一边！
上面例子：
下标为1与8的高中，8的高比较矮，则高为7，而底的长度为
8-1=7，则桶的容量为7X7=49！
在讲解优解前，我们可以先讲讲暴力解法！
暴力枚举
两层for循环能解决问题，但是题目可能会超时！时间复杂度： O(n^2^ )
利用单调性，使用双指针解决问题
以一组数6、2、5、4为例，我们尝试找找其中的规律！
我们以最宽的两条线开始，体积V= 4 X 3 = 12 ，接着我们以4开始向内枚举可以发现，向内枚举时，宽度X是一直在减小的！而高度H不是减小就是不变！，比如枚举待数据2！高度为2 ，宽度为2，V肯定减小，而枚举到5！高度为4，不变，宽度为1，V体积减小，所以这个时候就可以把这个4排除掉，用内部 其他数去枚举！
两个指针从数组的两端开始，数据小的一边向内移动！移动后计算体积并更新！再移动数据小的指针！
用这个方法持续遍历一遍就可以找到最大值，所以时间复杂度为O(n)！并且可以把每次的体积记录在被次被排除的数据位置，空间复杂度也小！或者准备一个最大值变量来存储！
代码实现！
有效三角形的个数（画图）
有效三角形的个数
本题有个注意事项！就是有相同数字时，要注意两个相同数字之间的不同组合！
在讲解题目前，先补充一个知识点！
给出三边，判断是否能组成三角形时，我们会使用这个方法来判断！
a + b > c , b + c > a , a + c > b，这个方法我们当然知道，但是这是要做三次比较呀！而讲数据排序，就只需要做一次排序，即 a + b > c ! 因为c是>= a ，b 的 ，所以c + a/b > b/a 的！
暴力解法
利用单调性，使用双指针算法来解决问题！
这题为何可以使用单调性呢？主要是上面提到的 a + b > c的小巧思！
数据[2,2,3,4,5,9,10]这组数据已经是有序的，这是前提！
我们现在判断是否为三角形是用 a + b > c 的方法，拿a，b两个小的数和一个大的数比较，我们现在就先确定最大的数，使用现在就是固定最大的数，为10，即 a + b > 10，现在就是对10后面的数据进行枚举，但是这个枚举不是单纯的枚举，那和上面的暴力枚举没啥区别，我们就在10后面那一堆数据中找到最大和最小值，并用right和left两个指针指向！left代表啊，right代表b，此时来判断 a + b > 10！，有两种处理情况！ a + b > c 或者 a + b <= c
此时a = 2 ，b = 9 ， a+b = 11 > 10 为第一种情况，此时我们要知道一个性质，就是既然最小的a = 2 ，加 b=9可以大于c，那么a和b之间的数据都可以和b相加满足了，所以不需要再判断，直接记录有right-left个数！记录后此时9已经枚举完了往下一个元素判断即right--！所以此时a=2、b=5，a+b < c，为第二种情况，a到b之间的数都是小于b的数据，既然a + b < c，那么a 与a和b之间的数之和肯定也是小于c的，所以可以直接不判断，跳过a的判断了，向下一个区间判断！即 left++，由此往复，知道指针相遇，说明这个固定的最大数c已经判断完了，可以找下一个最大数了，开始下一循环！
方法：
1、先固定最大数
2、再最大数的左区间内，使用双指针算法，快速统出符合要求的三元组的个数！
时间复杂度为O(n^2^)！
代码：
和为s的两个数（vector返回值拓展{ x,x}）
和为s的两个数
解题思路
暴力解题
这题的暴力解法很容易，直接两层循环！将数据每个数和这个数后面的数据枚举计算 ！
这个暴力枚举的时间复杂度为O(n^2^)！
利用单调性，使用双指针算法解决问题！
我们一开始就用双指针left和right指向最小最大值，而sum = left + right ；要和t(目标值)比较，而这样比较有三种情况！sum > t、sum < t、sum = t，遇到三种情况有不同的处理
以数据[2,7,11,15,19,21] t = 30为例子！此时left -> 2 ；right-> 21 ，sum < 30 ,这个时候我们观察数据！数据是有序的，既然2与最大值21相加还小于30，使用2已经没有和之间数据比较的必要了，使用此时不用再用2去枚举了，直接跳过，即当sum < Target时！left++！
当sum > Target！说明此时最大值加上此时的最小值还是大于Target，说明这个最大值没有枚举的意义了，跳过此时的数据，即right--！
最后是sum = target，此时相等说明找到符合要求的数据，将数据嵌入新的vector并返回！
代码
{ price[left],price[right]}；vector隐式返回方式！
C++语法：当要返回vector数据并且只有两个数据的时候，可以使用return {nums[left],nums[right]};这个是C++的语法，会做隐式转换为vector并返回！
这个错误是leetcode的特色！意思是并不是所有的路径都有返回值！认为如果if语句未成立就会导致函数无法退出！所有在循环外做一个返回的操作！
三数之和(unordered_set)
三数之和
i,j,k三个下标不等！且输出三元组不重复，内部数据元素不重复！且输出三元组数据的顺序没有要求！
本题的难点是去重复三元组的操作！
暴力解法
讲解暴力解法的原因是很多优秀解法以及最优解都是在暴力解题的基础上，通过其他算法思想推出来的！
暴力枚举 + 去重复
为了方便去重，做个排序方便检查！
排序 + 暴力枚举 + 去重复（利用unordered_set去重）
将三元组插入到unordered_set[1]中就可以完成去重
时间复杂度O(n^3^)
最优解题
排序 + 双指针
为了优化查重而排序，想到排序，即有了有序数组时就要想到二分查找和双指针来解题！
这里是用双指针来解决！
双指针可以将暴力解题的时间复杂度降低一维！
先排序 ， 之后固定一个数a ， 在这个数后面的区间内，利用“双指针算法”快速找到两个数的和等于-a即可！
处理细节问题：
1、去重
我们要学习不用容器解决问题的方法！
我们现在知道数据是有序的！所有相同数据是在一起的！当前一个数满足时候，就没必要移动指针到该位置了，因为重复了！所以是在找到一个结果时，对双指针的处理问题了！
即找到一个结果之后，left和right指针要跳过重复的元素！
并且固定数也要注意不要重复，因为我们已经固定过这个数了，所以不用在处理这个数了！也是跳过相同数！
所以，去重 要注意 固定数和双指针有结果的时候！
去重过程要避免越界！ 如0,0,0,0的数据！
2、不漏
为什么讲解不漏，以为上一题两数之和的解题是，找到符合数就退出，这题不一样，找到第一个符合的两数，可能后面还有数据符合！所有两指针找到对应数的反应不是退出而是继续移动指针
即找到一种结果之后，不要“停”，缩小区间，继续寻找！
总结
这题解题思路并不是最重要的！这个题的细节问题才是最重要的！时间复杂度为O(n^2^)！
代码
四数之和
四数之和
题目和上题类似！a,b,c,d四个下标不等！且输出四元组不重复，内部数据元素不重复！且输出四元组数据的顺序没有要求！
暴力解法
排序 + 暴力枚举 + 利用set去重
时间复杂度为O(n^4^)，肯定超时！
最优解法
排序 + 双指针
1、依次固定一个数a；
2、在a的后面区间内，利用“三数之和”的算法思路找到三个数，使这个三个数的和等于target - a即可！
三数之和的算法思想
1、依次固定一个数b；
2、在b后面的区间内，利用双指针找到两个数，使这个两个数的和等于
target - a - b即可！
代码实现：
这里会发现报错！上面的报错信息告知为由数据溢出的风险，即-1294967296 - 1000000000有可能溢出的！计算结果会超出储存范围了，这里要如何处理呢？将对应变量扩大存储范围，这里使用long long即可，注意对后续数据进行强转！
删除有序数组中的重复项
删除有序数组中的重复项
本题为有序数组，需要用双指针的方法来解决本题问题，查找重复数据，并且去除，要求剩下的数据要保持原来的顺序，返回去除重复数据后数组的长度！
暴力解法
枚举数组每一个数据（循环），每个数据为对比值，遍历（循环）数组去找相同值！发现相同数据，就将后面的数据往前覆盖（循环）
这样的解题的时间复杂度为O(n^3^)！
利用单调性，使用双指针解法
我们可以使用双指针，left，right指针，left指针指向对比值！从0开始，right从1开始，用于查找不重复值，以数据[0,0,1,1,1,2,2,3,3,4]为例子讲解
left = 0， right = 1，若left 大于等于 right的数据相等，right++找大于left处的数据，在2处找到，直接在left+1处直接覆盖，并且left++，ret++（ret++是因为完成了一个值的查重），对比下一个数据，right不需要回退，继续在2处判断！以此类推直到right等于数组长度，退出！返回ret！
unordered_set是无序、无重复的关联容器，底层哈希表保证平均 O(1) 的高效增删查； 接口和set基本一致，但遍历无序，内存占用更高，迭代器稳定性稍差； 选型原则：无需有序时优先用unordered_set（效率更高），需要有序 / 范围查询时用set。
