一、概念和分类
双指针是一种用两个指针协同移动来减少遍历次数、降低时间复杂度的思路。
常见的有对撞指针和快慢指针。
1.对撞指针
•对撞指针是从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环）。
2.快慢指针
•快慢指针的基本思想是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。这种⽅法对于处理环形链表或数组⾮常有用。通常是慢指针走一步，快指针走两步，实现一快一慢。
二、题目
1、移动零 ：283. 移动零 - 力扣（LeetCode）![]()
https://leetcode.cn/problems/move-zeroes/description/
1. 题目描述：
给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入:nums =[0,1,0,3,12]
输出:[1,3,12,0,0]
示例 2:
输入:nums =[0]
输出:[0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
2.思路：
这个题是要求我们把数组分为两块区间，把零都移到后半块区间去。所以我们可以使用两个“指针”，⽤⼀个 cur指针来扫描整个数组，另⼀个dest指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。 在遍历期间，使[0, dest]的元素全部都是⾮零元素，[dest + 1, cur - 1]的 元素全是零。
注意：这里的指针并不真的是两个指针，而是模仿指针的行为
3.代码实现：
1.初始化 cur = 0（⽤来遍历数组），dest = -1（指向⾮零元素序列的最后⼀个位置。 因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1）。
2. cur循环遍历每个元素，会遇到两种情况。cur遇到0的时候直接cur++就好，dest不做改变，因为要确保[dest+1, cur-1]之间的元素都是0；如果cur遇到非0元素，让dest++之后，再去和cur的元素交换。这样下来就可以把数组划分完成了。以下是c++代码，可直接AC。
class Solution { public: void moveZeroes(vector<int>& nums) { for(int cur = 0, dest = -1; cur < nums.size(); cur++) { if(nums[cur])//处理非0元素 { swap(nums[cur], nums[++dest]); } } } };2.复写零：1089. 复写零 - 力扣（LeetCode）![]()
https://leetcode.cn/problems/duplicate-zeros/description/
1.题目描述：
给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。
示例 1：
输入：arr = [1,0,2,3,0,4,5,0]输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：输入：arr = [1,2,3]输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]
提示：
1 <= arr.length <= 1040 <= arr[i] <= 9
2.思路：
根据题意，如果我们从前向后复写的话，会导致后面的数据被掩盖掉，所以这个题我们的思路是从后往前复写。
因为我们是从后往前复写，所以我们要找到最后一个复写的元素，这个时候就要用到我们的双指针了。
如果可以开辟一个和原数组一样大小的新数组的话，我们的可以定义两个指针，cur 和 dest，cur指向当前数组，dest指向复写的数组。这是，我们会发现，当cur指向0时，dest要复写两次，cur不指向0时，dest只需复写一次，当dest达到数组的结尾时，cur会指向最后一个复写的元素。
所以，我们根据这个思路，我们可以两个指针定义到原数组上，进行同样的操作，就可以找到最后一个复写的元素了。然后在执行从后往前的复写操作。
3.代码实现：
定义两个指针，cur 和 dest，cur = 0， dest = -1，dest要指向最后一个复写的元素，开始时是-1；
值得注意的是，有一个情况要处理，例如在这组数据下[1,0,2,3,0,4]，dest = n；所以我们要处理一下边界问题。以下是c++代码，可直接AC。
class Solution { public: void duplicateZeros(vector<int>& arr) { int cur = 0, dest = -1; int n = arr.size(); // 1.先找到最后一个数 while(cur < n) { if(arr[cur] != 0) dest++; else dest += 2; if(dest >= n-1) break;//dest走到结尾了，cur已经指向最后一个元素了 cur++; } // 2.处理边界情况 if(dest == n) { arr[n-1] = 0; dest -= 2; cur--; } // 3.完成复写 while(cur >= 0) { if(arr[cur] != 0) { arr[dest--] = arr[cur--]; } else{ arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };3.快乐数：202. 快乐数 - 力扣（LeetCode）![]()
https://leetcode.cn/problems/happy-number/description/
1.题目描述：
编写一个算法来判断一个数n是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
- 如果这个过程结果为1，那么这个数就是快乐数。
如果n是快乐数就返回true；不是，则返回false。
示例 1：
输入：n = 19输出：true解释：12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1示例 2： 输入：n = 2输出：false
2.思路：
根据题意，我们把 “对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和” 记为操作x。当我们对这个数不断执行x时，这个过程一定会进入死循环。要么是变换到1之后，一直循环1这个数字，那么这个数就是题目要求的快乐数；要么一直在曾经变换过的数据中循环，一直变不到1。
那么一定为什么会进入死循环呢，这就要用到鸽巢原理了。因为int的最大值为 2^31-1 == 2147483647，我们选一个更大的数 9999999999，那么它的变换为 9^2 * 10 = 810；所以变化的区间一定在[1,810]这个区间内。当经历811次变换时，一定会进入循环；
所以，根据上述思路，我们可以使用快慢指针在循环中，快指针一定会追上慢指针的特点来解决问题。我们只需要判断相遇位置的值是否为1即可。
3.代码实现：
class Solution { public: // 操作x int tmp(int n) { int a = 0; while(n){ int t = n % 10; a += t * t; n /= 10; } return a; } bool isHappy(int n) { int slow = n, fast = tmp(n); while(slow != fast){ // 走一步 slow = tmp(slow); // 走两步 fast = tmp(tmp(fast)); } return slow == 1; } };4.盛最多水的容器 ：11. 盛最多水的容器 - 力扣（LeetCode）![]()
https://leetcode.cn/problems/container-with-most-water/description/
1. 题目描述:
给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]输出：49解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
2.思路：
方法一：可以直接暴力枚举，但会超时，所以这里不做详细介绍；
方法二（对撞指针）：设两个指针left ， right 分别指向容器的左右两个端点，所以容器的容积 v = (right - left) * min( height[right], height[left])；根据这个式子，我们假设左边界小于右边界，如果此时我们固定⼀个边界，改变另⼀个边界，水的容积会有如下变化形式：
3.代码实现：
class Solution { public: int maxArea(vector<int>& height) { int left = 0, right = height.size()-1; int maxnum = 0; while(left < right) { int tmp = (right - left) * min(height[left], height[right]); maxnum = max(tmp, maxnum); if(height[right] < height[left]){ right--; } else{ left++; } } return maxnum; } };5.有效三角形的个数：
611. 有效三角形的个数 - 力扣（LeetCode）https://leetcode.cn/problems/valid-triangle-number/description/
1.题目描述：
给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入:nums = [2,2,3,4]输出:3解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:
输入:nums = [4,2,3,4]输出:4
2.思路：
在判断3条边是否可以组成三角形的条件是，任意两条边之和大于第三条边。那如果这三条边是有序的，那么，只用判断小的两条边之和大于第三条边即可。
方法一：暴力三重循环，不做详解；
方法二（排序 + 双指针）：
根据上述分析，我们上来就可以对整个数组排序，然后固定一个边界 flag，利用对撞指针left 和 right 来寻找 [letf , right]（在flag的左边，也就是比flag小的区间） 这个区间满足nums[left] + nums[right] > nums[flag]的二元组；
如果这个区间[letf , right]有满足条件的，说明区间[letf , right-1]上的所有的元素和nums[right] 组成的二元组都满足条件，一共有right - left种；此时 right 位置的元素的所有情况相当于全部考虑完毕，right--，进⼊下⼀轮判断。
如果nums[left] + nums[right] <= nums[flag]，直接让left++即可；
3.代码实现：
class Solution { public: int triangleNumber(vector<int>& nums) { int ret = 0; // 先优化，将数组排序 sort(nums.begin(),nums.end()); // 利用双指针解决问题，先固定最大的数 int flag = nums.size()-1; while(flag >= 2){ int left = 0, right = flag - 1; while(left < right){ if(nums[left] + nums[right] > nums[flag]){ ret += right - left; right--; } else{ left++; } } flag--; } return ret; } };
