双指针移动零移动零这里的解题思想是数组的划分数组分块用到双指针算法此处指针用数组下标来表示这里的数组分块总的分为两大部分处理过和待处理部分按题目要求数组前侧为处理过部分后侧为待处理而而处理部分内部也有两个分区非0区和0区有两个指针 一个是cur 当前位置 从做数组的整体遍历的还有一个是dest 表示已处理区间内非0 元素的最后一个位置所以有了三个分区 [0,dest] [dest 1 , cur -1] [curn-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数据的不同dest1或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个巢穴 n1个鸽子 --- 至少有一个巢里面的鸽子数大于1这道题整数的最大值为int整型的最大值2^31^ 约等于 2.1 X 10^9^ 那么找个比这个数大一点的数10个99999999999那么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-17则桶的容量为7X749在讲解优解前我们可以先讲讲暴力解法暴力枚举两层for循环能解决问题但是题目可能会超时时间复杂度 O(n^2^ )利用单调性使用双指针解决问题以一组数6、2、5、4为例我们尝试找找其中的规律我们以最宽的两条线开始体积V 4 X 3 12 接着我们以4开始向内枚举可以发现向内枚举时宽度X是一直在减小的而高度H不是减小就是不变比如枚举待数据2高度为2 宽度为2V肯定减小而枚举到5高度为4不变宽度为1V体积减小所以这个时候就可以把这个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 的方法拿ab两个小的数和一个大的数比较我们现在就先确定最大的数使用现在就是固定最大的数为10即 a b 10现在就是对10后面的数据进行枚举但是这个枚举不是单纯的枚举那和上面的暴力枚举没啥区别我们就在10后面那一堆数据中找到最大和最小值并用right和left两个指针指向left代表啊right代表b此时来判断 a b 10有两种处理情况 a b c 或者 a b c此时a 2 b 9 ab 11 10 为第一种情况此时我们要知道一个性质就是既然最小的a 2 加 b9可以大于c那么a和b之间的数据都可以和b相加满足了所以不需要再判断直接记录有right-left个数记录后此时9已经枚举完了往下一个元素判断即right--所以此时a2、b5ab 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、依次固定一个数a2、在a的后面区间内利用“三数之和”的算法思路找到三个数使这个三个数的和等于target - a即可三数之和的算法思想1、依次固定一个数b2、在b后面的区间内利用双指针找到两个数使这个两个数的和等于target - a - b即可代码实现这里会发现报错上面的报错信息告知为由数据溢出的风险即-1294967296 - 1000000000有可能溢出的计算结果会超出储存范围了这里要如何处理呢将对应变量扩大存储范围这里使用long long即可注意对后续数据进行强转删除有序数组中的重复项删除有序数组中的重复项本题为有序数组需要用双指针的方法来解决本题问题查找重复数据并且去除要求剩下的数据要保持原来的顺序返回去除重复数据后数组的长度暴力解法枚举数组每一个数据循环每个数据为对比值遍历循环数组去找相同值发现相同数据就将后面的数据往前覆盖循环这样的解题的时间复杂度为O(n^3^)利用单调性使用双指针解法我们可以使用双指针leftright指针left指针指向对比值从0开始right从1开始用于查找不重复值以数据[0,0,1,1,1,2,2,3,3,4]为例子讲解left 0 right 1若left 大于等于 right的数据相等right找大于left处的数据在2处找到直接在left1处直接覆盖并且leftretret是因为完成了一个值的查重对比下一个数据right不需要回退继续在2处判断以此类推直到right等于数组长度退出返回retunordered_set是无序、无重复的关联容器底层哈希表保证平均 O(1) 的高效增删查 接口和set基本一致但遍历无序内存占用更高迭代器稳定性稍差 选型原则无需有序时优先用unordered_set效率更高需要有序 / 范围查询时用set。