目录
双指针的简单介绍
双指针是一种常用的算法技术，主要用于处理数组、链表等线性结构中的问题。它通过使用两个指针在数据结构中同时移动，从而达到有效解决问题的目的。这种方法通常能够减少空间复杂度或时间复杂度，或者使代码更加简洁。
它可以是数组的下标，亦或是链表的第k个值。
双指针的类型
两个指针分别从数组的两端向中间移动。
常用于寻找数组中两数之和、判断回文字符串、合并两个有序数组等问题。
两个指针都从同一方向移动，通常一个指针移动得快，另一个移动得慢。
常用于寻找子数组、滑动窗口问题、链表环检测等。
下面我将会从8个力扣的题来讲解利用双指针来解题。
每个题将会从对题目的意思介绍，算法的原理，编写代码的注意点
有的题目机译没什么问题就不一句一句解释了
题目一：283. 移动零 - 力扣（LeetCode）
题目意思解释
该题目给了一个数组nums，然后让你编写一个函数，对数组进行操作后，使得该数组分为两部分，0全部在数组的后半部分，前半部分全为非0，并且非零部分的元素还保持着原来数组的相对位置，相对位置的意思就为：原数组中a在b前面，那么进行操作过后还是a在b前。并且，该题目还要求只能在数组的原地进行操作。
算法原理
如果我们先抛开计算机的编程思想，我们在现实生活中遇见这样问题，那么我们肯定想着先按照相对位置把所有非0元素拿出来排好，在把0依次放在其后，但是在编程中这就不是在数组原地进行操作。
经过思考后发现可以依次交换如果两个相邻的数，只需要把非0的与0进行交换。
就比如只需要先1 0交换后再 0 3，最后0 12就达到了要求，那么我们把这种思想转换为编程思想即可，这种思想就为双指针思想。
我们只需要定义两个“指针”
然后把数组分为两个区间，其中又分为三个小区间。
对于指针的操作如下：
这里用的是同向指针
代码实现
class Solution {
public:
void moveZeroes(vector& nums) {
int cur=0;
int dest=0;
while(dest<nums.size())
{
if(nums[dest])
{
swap(nums[dest], nums[cur]);
++cur;
}
++dest;
}
}
};
题目二：1089. 复写零 - 力扣（LeetCode）
题目意思解释
给了一个长度固定的整形数组，然后将所有0全部复写一边，并将其后面的所有元素全部向右移动，还需要对该数组就地修改，不返回任何东西。
那么画一个简单的图来解释一下题目意思
算法原理
理解题目后，如果对时间复杂度比较敏感，算法就必须从后往前进行遍历。这是因为如果从前往后依次复写，可能会出现覆盖问题，并且时间复杂度将达到 O(n²)。
采用双指针算法，从后往前遍历会更加高效。以第一个测试用例为例，我们可以清楚地知道最后一个操作数是4，因此只需将4 覆盖到最后一个0 的位置，然后再依次将0复写到前面的两个位置。这样，我们可以高效地向前遍历并进行覆盖。
在实现时，可以参考第一题的代码，使用双指针的方法来完成。以下是操作示意图，具体实现可以根据这个思路进行编码。
那么重要的怎么明确找到最后一个位置，也就是怎么代码实现使其cur指针指向的是4，而不是0或者5，
那么这里是用到的快慢指针，我先直接给出代码，代码所要实现的就为
如果arr[cur]为0的话dest+=2
如果arr[cur]不为0的话dest++
dest走到最后一个元素结束
最后cur++
int n=arr.size();
int dest=-1,cur=0;
while(dest=n-1) break;
cur++;
}
在编写这部分代码时，我也有很多疑问，比如为什么将 dest 初始化为 -1 而不是0，cur 又为什么初始化为0。
要理解这些初始化的原因，从结果反推起始的设置会更加清晰。
从结果倒推，我们可以得出以下结论：因此，dest 初始化为 -1，而 cur 初始化为0。
但是根据算法原理一点点实现代码，然后运行提交，会报越界的错误，这是因为有种特殊的情况，比如下面的这个数组：
经过上面的代码后，cur与dest的指向情况如下：
因此，当 dest 等于 n 时，需要进行特别处理。
代码实现
class Solution {
public:
void duplicateZeros(vector& arr) {
int n=arr.size();
int dest=-1,cur=0;
while(dest=n-1) break;
cur++;
}
if(dest==n)
{
arr[n-1]=0;
dest-=2;
cur--;
}
while(cur>=0)
{
if(arr[cur])
{
arr[dest]=arr[cur];
cur--;
dest--;
}
else
{
arr[dest]=arr[cur];
dest--;
arr[dest]=arr[cur];
dest--;
cur--;
}
}
}
};
题目三：202. 快乐数 - 力扣（LeetCode）
题目意思解释
题目的意思很好理解，那么这里我就不在解释了，我说明需要注意的地方：这个题中又这样一句话：然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1
永远的无限循环就是他题目中的2，他会陷入循环，并且循环中一直不会变为1.
但起始1也是一种循环，但他的循环一直为1.
算法原理
这道题的算法原理其实是引用了环形队列的快慢指针的思想，（题目：141. 环形链表 - 力扣（LeetCode）））
我这里举一个生活中跑步的案例解释一下：假设小明与小刚同学同时从宿舍出发去操场跑步，小明的速度是小刚速度的二倍，那么总有那么一秒初（不是一秒中也不是末）小刚与小明会相遇。
所以我们以这种的方法就可以判断是以1循环还是不规则的循环
代码实现
class Solution {
public:
int bitsum(int n)
{
int ret=0;
while(n)
{
int t=n%10;
ret+=t*t;
n/=10;
}
return ret;
}
bool isHappy(int n) {
int slow=n,fast=bitsum(n);
while(slow!=fast)
{
slow=bitsum(slow);
fast=bitsum(bitsum(fast));
}
return slow==1;
}
};
题目四：11. 盛最多水的容器 - 力扣（LeetCode）
题目意思解释
依旧是这一题的意思很好理解，需要提一嘴的就是一个木桶所能装多少水是由其短板决定的。所以这一题的容器高是由两端木板中的短板决定。
算法原理
对于一个容器的容量计算公式 v=w*h
那么我们还是利用双指针来解决这道题，需要用到的是相向双指针，定义一个right指针，与left指针，需要解决的是什么情况left++，什么情况下right--，
从公式来说，无论是left++，还是right--，他都会使得w减小，但是w减小的话，如果v要想增加，那么只能使得h增大。然而一个容器内的h是由短板决定，所以就很容易想到要将小的那个进行调整。
这也很好理解，如果我们对高的进行调整，就算遇到一个更大的数，那么h依旧不会发生改变，遇见小的只会更小，不符合我们的要求。
代码实现
class Solution {
public:
int maxArea(vector& height) {
int n=height.size();
int r=n-1,l=0;
int mx=0;
while(r>l)
{
int w=r-l;
int h=min(height[r],height[l]);
mx=max(mx,h*w);
if(height[r]>height[l]) l++;
else r--;
}
return mx;
}
};
题目五： 611. 有效三角形的个数 - 力扣（LeetCode）
题目意思解释
同样这道题的描述依旧很详细，需要提一嘴的就是如果该数组为[ 2 , 2 , 2 , 3 , 4 ]，
那么2 , 2 ，3 与2 , 2 , 3，是不同的两个组，应该计为2，不为1。
同样需要补充的一点就是构成三角形的规定：任意两边之和大于第三边。
算法原理
我们这道题就是运用到的为 任意两边之和大于第三边 ，但是如果将三个数都进行两两组合，就显得过于麻烦，这时候需要我们先排序，排序之后，任取三个数，相对位置的前两个数相加如果大于第三个，那么其余组合一定大于另外一边。这也很好理解，如果三个数两个小的数相加大于最大的哪一个，那么其余组合一定成立。
因为有三个操作数，那么是不是要用三指针解决呢？
其实不然，我们不妨套一层循环，定一，另外两个用双指针解决子问题。
那么需要解决的就是定谁？
令 两个小的数为 a ，b，最大的为 c ，如果a+b>c则构成三角形
如果定a，那么b与c必须要定位双向双指针，在a+b<=c时，b调大或c调小都可以，会有歧义，但是a+b>c时，没有可以调整的指针使得当前状态改变。定b也是这样分析。
所以要定c
如果此时a+b>c那么如果a增大已经为a+b>c，所以此时只要a小于b都可以构成三角形，
这时一共有b-a个数。
如果a+b<=c，那么就需要调整b，使得找到a+b>c的情况在进行上面操作。
代码实现
class Solution {
public:
int triangleNumber(vector& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
int ret = 0;
for (int c = n - 1; c >= 2; c--) {
int a = 0, b = c - 1;
while (b > a) {
if (nums[a] + nums[b] > nums[c]) {
ret += b - a;
b--;
} else {
a++;
}
}
}
return ret;
}
};
题目六：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
题目意思解释
题目描述很详细，并且也没有需要注意的，那么这就不解释了。
算法原理
这一道题应该算是所有题中最好写的，甚至比力扣第一题还简单好多。
这就不在多说了。
只给一点提示：需要用的双指针类型为双向双指针。
需要注意的是，自己熟悉一下本题的返回形式，还有注意保证函数在所有情况下都要有返回值，在没有找到的情况下，力扣一般是返回负数的。
代码实现
class Solution {
public:
vector twoSum(vector& price, int target) {
sort(price.begin(),price.end());
int n=price.size();
int r=n-1,l=0;
while(r>l)
{
if(price[r]+price[l]>target)
{
r--;
}
else if(price[r]+price[l]<target)
{
l++;
}
else{
return {price[l],price[r]};
}
}
return {-1,-1};
}
};
题目七：15. 三数之和 - 力扣（LeetCode）
题目意思解释
同样这道题理解起来很容易，但是需要注意的一点就是：[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，并且这个三元组还不能重复，比如测试用例的一，其中构成0的三元组中有两个[-1,0,1]，但是只算一个。
算法原理
其实算法实现思路还是与构成三角形的那个一样还是定一，然后剩余两个用双向双指针法。如果是自己能完全不参考任何代码可以写出，那么这一题完全不是问题。
注意：
一定要符合题中的要求，三元组不可以重复，一定要保证每一个三元组不同，那么需要注意的就是两次的first或者second或者third不可以相同，需要去重。
代码实现
代码实现给两个版本，一个是for循环，一个是while循环
class Solution {
public:
vector> threeSum(vector& nums) {
vector> ret;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int first=0;first0) break; //小优化 如果first大于0 ，first又为最小，那么无论如何都构不成0
if (first>0 && nums[first] == nums[first - 1])// 去重
{
continue;
}
int third=n-1;
int second=first+1;
int target = -nums[first];
while(secondtarget)
{
third--;
}
else if(nums[second]+nums[third]<target)
{
second++;
}
else
{
ret.push_back({nums[first],nums[second],nums[third]});
second++,third--;
while(second<third && nums[second]==nums[second-1]) second++;// 去重
while(second<third && nums[third]==nums[third+1]) third--;// 去重
}
}
}
return ret;
}
};
class Solution {
public:
vector> threeSum(vector& nums) {
vector> ret;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int first=0;first0 && nums[first] == nums[first - 1])
{
continue;
}
int third=n-1;
int target = -nums[first];
for(int second=first+1;secondfirst+1 && nums[second]==nums[second-1])
{
continue;
}
while( third>second&& nums[second]+nums[third]>target)
{
third--;
}
if(second>=third) break;
if (nums[second] + nums[third] == target)
{
ret.push_back({nums[first],nums[second],nums[third]});
}
}
}
return ret;
}
};
题目八：18. 四数之和 - 力扣（LeetCode）
题目意思解释
意思与上一题完全一致
算法原理
同样为双指针，但是需要定二，另外两个为双向双指针。其实这道题就是在外壳套一个三数之和。
很简单。
代码实现
代码实现给两个版本，一个是for循环，一个是while循环
class Solution {
public:
vector> fourSum(vector& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector> ret;
for (int first = 0; first < n; first++)
{
if (first > 0 && nums[first] == nums[first - 1])
{
continue;
}
for (int second = first + 1; second < n; second++)
{
if (second > first+1 && nums[second] == nums[second - 1])
{
continue;
}
int fourth = n - 1;
int third=second+1;
long long ans = (long long)target - nums[first] - nums[second];
while(third ans)
{
fourth--;
}
else if(nums[third] + nums[fourth] < ans)
{
third++;
}
else
{
ret.push_back({ nums[first],nums[second],nums[third],nums[fourth] });
third++,fourth--;
while(third<fourth && nums[third]==nums[third-1]) third++;
while(third<fourth && nums[fourth]==nums[fourth+1]) fourth--;
}
}
}
}
return ret;
}
};
class Solution {
public:
vector> fourSum(vector& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector> ret;
for (int first = 0; first < n; first++)
{
if (first > 0 && nums[first] == nums[first - 1])
{
continue;
}
for (int second = first + 1; second < n; second++)
{
if (second > first+1 && nums[second] == nums[second - 1])
{
continue;
}
int fourth = n - 1;
long long ans = (long long)target - nums[first] - nums[second];
for (int third = second + 1; third < n; third++)
{
if (third > second + 1 && nums[third] == nums[third - 1])
{
continue;
}
while (fourth > third && nums[third] + nums[fourth] > ans)
{
fourth--;
}
if (third >= fourth) break;
if (nums[third] + nums[fourth] == ans)
{
ret.push_back({ nums[first],nums[second],nums[third],nums[fourth] });
}
}
}
}
return ret;
}
};
到这里就结束了，
那么为了检测，可以去力扣上搜一些双指针的题去练习
