一、概念和分类双指针是一种‌用两个指针协同移动来减少遍历次数、降低时间复杂度的思路。常见的有对撞指针和快慢指针。1.对撞指针•对撞指针是从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环。2.快慢指针•快慢指针的基本思想是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。这种⽅法对于处理环形链表或数组⾮常有用。通常是慢指针走一步快指针走两步实现一快一慢。二、题目1、移动零 283. 移动零 - 力扣LeetCodehttps://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 - 12.思路这个题是要求我们把数组分为两块区间把零都移到后半块区间去。所以我们可以使用两个“指针”⽤⼀个 cur指针来扫描整个数组另⼀个dest指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur在扫描的过程中遇到的不同情况分类处理实现数组的划分。 在遍历期间使[0, dest]的元素全部都是⾮零元素[dest 1, cur - 1]的 元素全是零。注意这里的指针并不真的是两个指针而是模仿指针的行为3.代码实现1.初始化 cur 0⽤来遍历数组dest -1指向⾮零元素序列的最后⼀个位置。 因为刚开始我们不知道最后⼀个⾮零元素在什么位置因此初始化为 -1。2. cur循环遍历每个元素会遇到两种情况。cur遇到0的时候直接cur就好dest不做改变因为要确保[dest1, cur-1]之间的元素都是0如果cur遇到非0元素让dest之后再去和cur的元素交换。这样下来就可以把数组划分完成了。以下是c代码可直接AC。class Solution { public: void moveZeroes(vectorint nums) { for(int cur 0, dest -1; cur nums.size(); cur) { if(nums[cur])//处理非0元素 { swap(nums[cur], nums[dest]); } } } };2.复写零1089. 复写零 - 力扣LeetCodehttps://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] 92.思路根据题意如果我们从前向后复写的话会导致后面的数据被掩盖掉所以这个题我们的思路是从后往前复写。因为我们是从后往前复写所以我们要找到最后一个复写的元素这个时候就要用到我们的双指针了。如果可以开辟一个和原数组一样大小的新数组的话我们的可以定义两个指针cur 和 destcur指向当前数组dest指向复写的数组。这是我们会发现当cur指向0时dest要复写两次cur不指向0时dest只需复写一次当dest达到数组的结尾时cur会指向最后一个复写的元素。所以我们根据这个思路我们可以两个指针定义到原数组上进行同样的操作就可以找到最后一个复写的元素了。然后在执行从后往前的复写操作。3.代码实现定义两个指针cur 和 destcur 0 dest -1dest要指向最后一个复写的元素开始时是-1值得注意的是有一个情况要处理例如在这组数据下[1,0,2,3,0,4]dest n所以我们要处理一下边界问题。以下是c代码可直接AC。class Solution { public: void duplicateZeros(vectorint 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. 快乐数 - 力扣LeetCodehttps://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输出false2.思路根据题意我们把 “对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和” 记为操作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. 盛最多水的容器 - 力扣LeetCodehttps://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]输出12.思路方法一可以直接暴力枚举但会超时所以这里不做详细介绍方法二对撞指针设两个指针left right 分别指向容器的左右两个端点所以容器的容积 v (right - left) * min( height[right], height[left])根据这个式子我们假设左边界小于右边界如果此时我们固定⼀个边界改变另⼀个边界水的容积会有如下变化形式1.容器的宽度⼀定变小。2.由于左边界较小决定了水的高度。如果改变左边界新的水面高度不确定但是⼀定不会超过右边的柱子高度因此容器的容积可能会增⼤。3。如果改变右边界⽆论右边界移动到哪⾥新的水面的高度⼀定不会超过左边界也就是不会超过现在的水面高度但是由于容器的宽度减小因此容器的容积⼀定会变小的。所以左边界和其余边界的组合情况都可以舍去。所以我们可以 left跳过这个边界继续去判断下⼀个左右边界。不断重复上述过程直到 left 和 right 相遇。期间产生的最大值就是最终答案。3.代码实现class Solution { public: int maxArea(vectorint 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. 有效三角形的个数 - 力扣LeetCodehttps://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]输出:42.思路在判断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(vectorint 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; } };