【优选算法 — 双指针】双指针小专题
和为 s 的两个数
题目描述
解法一：暴力枚举
暴力枚举，先固定一个数，然后让这个数和另一个数匹配相加，
如果当前的数 + 所有剩余的数 = target，则返回这两个数，否则固定下一个数；
所以暴力枚举只需要两层 for() 即可，但是这种解法实在太慢了，题目中给的是一个有序的数组，我们要利用数组有序的特性
解法二：利用单调性
利用单调性，使用双指针算法解决问题
先固定数组的首尾元素，固定好后，让两个数相加一下，看看能否使用单调性进行优化。
先不管 target 等于多少，这两个数之和 sum 无非就是三种情况
注意：sum 指的是 left 和 right 指向的数组元素之和
- sum < target
- sum > target
- sum = target
对比暴力枚举，利用单调性，使用双指针的算法的时间复杂度得到大大的优化；
暴力枚举需要拿固定的数，和所有剩余的数相加，但是解法二只需要让固定的数相加一次即可，就能判断是否舍弃当前固定的数了
时间复杂度
解法一 O(N^2)，解法二O(N)
编写代码
报错原因：
没有返回值，我们已经写了 return 语句，那么为什么编译器还会认为我们没有返回值呢？
我们必须保证所以的路径都要有返回值，而在上述代码，编译器不会管 while 语句中的 return 是否被执行，而是会考虑 只有 return 前的else 成立才会有返回值；
对于其他路径，如 else 不成立时，那么这个函数就没有返回值了，所以为了照顾编译器，强行返回一个值，就是告诉编译器一定会有返回值的：
快乐数
题目描述
第一种情况
return true
第二种情况
这个数在定义的过程中，会进入到一个没有 1 的环中，并且无限在环中循环，始终变不到 1
return false
题目解析
可以回忆OJ题：判断链表是否有环 ；
对于一个数，经过快乐数的定义变换后，是一定会成环的，并且题目也给出了提示；
如果题目没给提示，我们就需要验证是否会出现不成环的情况；其实是一定会成环的；
证明快乐数一定成环
鸽巢原理（抽屉原理）：n个巢，n+1 只鸽子，至少有一个巢，里面的鸽子数大于1
这道题的数据范围
最终，2^31 -1 的结果是一个10位整数，所以：
2^31 -1 < 999999999
快乐数转换(2^31 -1 ) < 快乐数转换（999999999）=81*10=810
所以快乐数的值的区间一定是[ 0，810 )，我们的巢穴出来了，我们随便找一个数，让他经过快乐数转换 811 次，转换的数一定是在 [ 0，810 )区间内的，在 转换 811 次之内，一定会出现重复的数，也就是一定会成环的。
所以对于这题，我们只需判断环中是否为1 ，来决定最终返回的boolean值
解法：快慢双指针
这里的指针并不是真正的指针，只是一种指针思想，在这题中，我们把变化过程中的数，抽象成指针；
- 1. 定义快慢指针；
- 2. 慢指针每次向后移动一步，快指针每次向后移动两步；
- 3. 对于判断链表是否有环，我们看的是快慢双指针最终能否相遇；
- 4. 对于快乐数，是一定会成环的，快慢双指针一定会相遇，我们只需要判断相遇点的值是否为1 ；
编写代码
因为每一次快乐数转换，都需要 求和 这个数的 每一位数 的平方，因此我们可以把这个过程封装成一个方法 bitSum() ，返回 n 这个数每一位上的平方和
盛最多水的容器
题目解析
right - left = 两根柱子之间的格子个数 = 宽度，返回 S 即可
解法一：暴力枚举
通过两层 for 循环，先让 left 固定左边的柱子， right 依次枚举右边的柱子；一轮枚举后，让 left 固定第二根柱子；但是这种做法是超时的；
解法二：对撞指针
算法原理
首先让 left 和 right 指向 6 和 4 ；
此时如果让 right 固定的是4，让left 向内枚举那么 wide 一直减小
在让 right 固定4，left 向内枚举时，会碰到三种情况：
- height[left] < height [right]；
- height[left] = height [right]；
- height[left] > height [right];
对于第一种情况，此时根据木桶原理，容器的高度是减小的，所以 S 减小；
第二种情况和第三种情况，根据木桶原理，容器的高度都是不变的，但是 wide 一直在减小；
所以无论是三种情况中的哪一种，向内枚举的 V 一直都是减小的；
所以拿 min( height[left] , height [right]) * wide 得到的 S，
如果固定其中任意一个指针，向内枚举一次，发现 S 减小，那就可以大胆的 舍弃当前 left 和 right 两个指针的较小值，固定较大值。
根据上面的思想，我们可以先固定 left 指向的1，让 right 向内枚举一次，得到的 S 是在减小的，因此可以大胆的舍弃 1，让left++；
此时，我们可以尝试着把 right 指向的 7干掉，让 right--，因为如果固定 7，那拿left 向内枚举，通过木桶原理，得到的 S 一直都是在减小的；
如果当前 left 和 right 是相同的，那么舍弃谁都可以，因为根据木桶原理，向内枚举体积都是在减小的；
总结
- S 是由宽度和木桶的短板决定的，在向内枚举时，优先向内移动两个指针中，指向较小值的指针；
- 每次枚举都求出对应的 S ，直到 left 和 right 对撞，返回这几次枚举中，S 的最大值
时间复杂度
解法一 O(N^2)；解法二 O(N)
编写代码
三数之和
三数之和(这个题一定一定一定要画图，空想会错很多，自己把这个题的代码写出来)
题目描述
我们根据题意，可以选出三组和为0的三元组，但是输出结果只要两组数：
所以是因为，第一组和第二组，选出的三元组，虽然顺序不一样，但是三元组的元素一样；
所以不可以包含重复三元组的意思，就是三元组的顺序不重要，只要的是两组三元组的元素不能完全一样。
这道题的难点是去重操作，我们先来想解法
解法一：先排序 + 暴力枚举 + 利用 set 去重
定义三层 for 循环，把能三个数之和等于0的，所有符合条件的三元组求出来，再对求出的组合去重；
去重操作，可以先把三元组从小到大排序，排好序之后再一 一 比对；
但是，如果在一个 length 非常大的数组中，找到了多对重复的，符合条件的三元组，那么一个一个找会非常麻烦。所以我们可以先把整个数组进行排序，然后再规定从左往右的顺序，进行所有三元组的枚举：
如果我们再一次找符合条件的三元组，就会发现找到的三元组已经是排好序的了；
比起刚刚的像刚刚没对数组排序，而是先找三元组，再对三元组排序 ；先对整个数组排序，再枚举所有三元组，更利于我们的查重操作
我们再利用 Java 中的 Set 集合，把所有得到的三元组，放入 HashSet 中，就会对数组去重，并且这是建立在排序整个数组，得到所有符合题意的三元组，才可以完美利用上 Set 的特性。
把所有三元组放入 Set 中，再把 Set 的结果拿出来作为返回值。
暴力枚举的时间复杂度：O( N^3 )，三层 for循环，去重操作针对的是有限个数的三元组，所以去重操作的时间复杂度可以忽略不记。
解法二：排序 + 双指针
用双指针，可以让时间复杂度降维，是非常优秀的算法，来看下面例子：
该数组已经排好序，利用暴力枚举时，我们是先固定一个数，然后在剩余区间中找到两个数组成符合题意的三元组
固定一个数，在剩余的数字，并且是有序的数字中，利用双指针快速找到符合题意的两个数。
处理细节问题：
去重；并且在上图的 left 和 right 区间中，有多对组合能相加凑出4，我们要把他们全部都找到；
- 不漏
- 去重
- 避免指针越界(在去重过程中会出现越界)
这三步操作是本题最重要的
否则
此时 left + right =4，此时 i，left，right拼接成第一对符合题意的三元组；但是我们还要继续这个过程，直到固定当前 i指针 的情况下，left 和 right 相遇。
所以不漏的操作，需要注意：
找到一种结果，不要让 left 和 right 停下来，继续缩小两个指针的区间 。
当然，如果在找到如上图的组合后，后面重复的 0 和 4 就不需要继续枚举了，所以我们去重，是要在找到一种结果之后，left 和 right 要跳过重复元素：
此时 i指针固定的第一个数的所有情况都已经枚举完毕，i++，此时我们发现，i指针 由指向了 -4：
又会出现重复的计算，因此我们去重要注意两个地方
- left 和 right 的去重
- 当使用完一次双指针算法之后，i 指针 也需要跳过重复元素
紧扣这两个情况，就能处理好去重操作
去重完后，我们还要处理双指针越界的情况：
通过刚刚的去重思想，来遍历上面的组合，会让双指针越界，因此我们在移动 i，left，right指针，来避免重复元素的时候，一定要处理指针越界的问题，我们结合代码，来讲解处理越界的情况。
还有一个小细节：
从煮啵写的代码来看，可以发现数据结构的基础很差~~~~
完整代码
修改： 下面i++，for循环就不要 i++了，不然会跳过要固定的下一个a
时间复杂度：O(N^2)
空间复杂度：用到了Arrays.sort()，快排，是递归产生的空间消耗，O(logN)
四数之和
解法一：排序 + 暴力枚举 + 利用 set 去重
解法二：排序 + 双指针
- 依次固定一个数 a
- 在 a 后面的区间内，找到“三数之和”思想 得到的三个数，使这三个数的和等于 target - a 即可
- 依次固定一个数 b
- 在 b 后面的区间内，利用“双指针”找到两个数，舍得这两个数的和等于“target - a - b”即可
整体思路，两层 for 循环中套一个双指针算法，这只是整体思路，还需处理细节问题：
处理细节问题：
(1)去重:
- left 和 right 要跳过重复的数
- 利用完双指针，b要跳过重复元素
- 利用“三数之和”后，a要跳过重复元素
(2)不漏（双指针在找到一组符合条件的数时，继续缩小区间）
编写代码：
解析：在计算的时候，会有溢出的风险，也就是计算结果和预期结果不符合：
时间复杂度：O(N^3)
空间复杂度：O(logN)，和三数之和的原因相同
原文地址：https://blog.csdn.net/2402_84916296/article/details/143495167
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！