????个人主页：小新_-

????个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”????

????欢迎各位→点赞???? + 收藏⭐️ + 留言????

????所属专栏： 计算机组成原理  欢迎订阅，持续更新中~~~

                      ​​

                               ✨让小新带着你快乐的学习吧~✨

目录

一、相关知识

（一）概念

（二）常见类型及应用场景

 1. 快慢指针 

2. 左右指针

三、优势 

 四、注意事项

二、经典题目练习

（一）移动零

1、题目描述

2、算法原理

3、代码实现

（二）复写零

1、题目描述：

2、算法原理：

3、代码实现

（三）快乐数

1、题目描述：

2、算法原理

3、代码实现

（四）盛容器最多的容器

1、题目描述

2、算法原理

3、代码实现

（五）有效三角形个数

1、题目描述

2、算法原理

3、代码实现

（六） 查找总价格为目标值的两个商品

1、题目描述：

2、算法原理：

3、代码实现：

（七）三数之和

1、题目描述

2、算法原理

3、代码实现

（八）四数之和

1、题目描述

2、算法原理

3、代码实现

---

一、相关知识

双指针算法是一种常用的算法技巧，主要用于解决数组或链表相关的问题。以下是对双指针算法学习总结：

（一）概念

 双指针是指使用两个指针来遍历数据结构，通常一个指针用于遍历，另一个指针用于辅助操作或记录特定位置。根据指针的移动方式和作用，可以分为不同类型的双指针算法，如快慢指针、左右指针等。

（二）常见类型及应用场景

 1. 快慢指针 

- 概念：两个指针在数据结构中以不同的速度移动。通常一个指针移动速度较快，称为快指针；另一个指针移动速度较慢，称为慢指针。
- 应用场景：
- 判断链表是否有环：快指针每次移动两步，慢指针每次移动一步。如果链表有环，快指针一定会追上慢指针。
- 寻找链表的中间节点：当快指针到达链表末尾时，慢指针正好位于链表的中间位置。

2. 左右指针

- 概念：两个指针分别从数据结构的两端开始向中间移动，或者从同一端开始向不同方向移动。
- 应用场景：
- 数组中的两数之和问题：通过左右指针遍历数组，找到满足特定条件的两个元素。
- 容器盛水问题：利用左右指针遍历容器的两侧，计算最大的盛水量。

三、优势 

1. 时间复杂度低：在一些情况下，双指针算法可以在一次遍历中解决问题，时间复杂度为 O(n)，相比其他算法可能更加高效。
2. 空间复杂度低：通常只需要使用两个指针变量，不需要额外的数据结构，空间复杂度为 O(1)。
3. 灵活性高：可以根据不同的问题场景灵活调整指针的移动方式和条件判断。

 
四、注意事项

1. 边界条件：在使用双指针算法时，需要注意指针的初始位置、移动条件和边界情况，避免出现指针越界或无限循环等问题。
2. 循环条件：正确设置循环条件，确保指针能够在合适的时候停止移动。
3. 问题的特殊性：不同的问题可能需要对双指针算法进行适当的调整和优化，不能生搬硬套。
 
总之，双指针算法是一种非常实用的算法技巧，通过合理地运用双指针，可以高效地解决许多数组和链表相关的问题。在学习和使用双指针算法时，需要深入理解其原理和应用场景，并通过大量的练习来掌握这种技巧。

二、经典题目练习

（一）移动零

题目链接：283. 移动零 - 力扣（LeetCode）

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、算法原理

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

1. 左指针左边均为非零数；
2. 右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

3、代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cur=0,dest=-1;//定义指针
        for(int i=0;i<nums.size();i++)//遍历数组
        {
            if(nums[cur]==0)//遇到零，cur跳过
            {
                cur++;
            }
            else
            {
                swap(nums[dest+1],nums[cur]);//遇到非零,dest+1与cur交换，然后各自加加
                 dest++;
                 cur++;
            }
        }

    }
};

（二）复写零

题目链接：1089. 复写零 - 力扣（LeetCode）

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 <= 104
• 0 <= arr[i] <= 9

2、算法原理：

我们只需要用两个指针来进行标记栈顶位置和现在需要放置的元素位置即可。我们用 top 来标记栈顶位置，用 i 来标记现在需要放置的元素位置，那么我们找到原数组中对应放置在最后位置的元素位置，然后在数组最后从该位置元素往前来进行模拟放置即可。

3、代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        } 
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (!arr[i]) {
                arr[j] = arr[i];
                j--;
            } 
            i--;
        }
    }
};

（三）快乐数

题目链接：202. 快乐数 - 力扣（LeetCode）

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

提示：

• 1 <= n <= 231 - 1

2、算法原理

使用 “快慢指针” 思想，找出循环：“快指针” 每次走两步，“慢指针” 每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为 1 引起的循环，是的话就是快乐数，否则不是快乐数。

3、代码实现

class Solution {
public:
int GetSum(int n)
{
    int sum=0;
    while(n)
    {
        int t=n%10;
         sum +=t*t;
        n/=10;
    }
    return sum;
}

   bool isHappy(int n) {
     int fast=GetSum(n);
     int slow=n;
     while(slow!=fast)
     {
        slow=GetSum(slow);
        fast=GetSum(GetSum(fast));
     }
     return slow==1;
    }
};

（四）盛容器最多的容器

题目链接：11. 盛最多水的容器 - 力扣（LeetCode）

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

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

2、算法原理

解法一（暴力解法）：遍历数组，每次计算一个值，最后取最大值。（不细讲）

时间复杂度：O（n*2）超时

解法二（双指针法）：

我们知道体积V=长度L(俩数距离)*高度H（俩数较小者）

根据数学知识我们知道

定义左右两个指针分别向数组中间走，可以看出，容器的容量就是两个指针指向的值中最小的那个值乘以两个指针之间的距离，可以用木桶效应来解释，即桶的容量取决于最短的那块木板。
第一次结果出来后，值较小的指针往中间走，这期间更新最大值，直到俩指针相遇。

我们先从题目中的示例开始，一步一步地解释双指针算法的过程。稍后再给出算法正确性的证明。

题目中的示例为：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
 ^                       ^
在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 min⁡(1,7)∗8=8

此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由两个指针指向的数字中较小值∗指针之间的距离两个指针指向的数字中较小值 * 指针之间的距离决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。

有读者可能会产生疑问：我们可不可以同时移动两个指针？ 先别急，我们先假设 总是移动数字较小的那个指针 的思路是正确的，在走完流程之后，我们再去进行证明。

所以，我们将左指针向右移动：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                    ^
此时可以容纳的水量为 min⁡(8,7)∗7=49。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^                 ^
此时可以容纳的水量为 min⁡(8,3)∗6=18。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
    ^              ^
此时可以容纳的水量为 min⁡(8,8)∗5=40。两指针对应的数字相同，我们可以任意移动一个，例如左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
       ^           ^
此时可以容纳的水量为 min⁡(6,8)∗4=24。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：min⁡(2,8)∗3=6，min⁡(5,8)∗2=10，min⁡(4,8)∗1=4

在我们移动指针的过程中，计算到的最多可以容纳的数量为 49，即为最终的答案。

3、代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1,ret=0;
        while(left<right)
        {
            int v=min(height[left],height[right])*(right-left);
             ret=max(v,ret);
            if(height[left]<height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;

    }
};

（五）有效三角形个数

题目链接：611. 有效三角形的个数 - 力扣（LeetCode）

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

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2、算法原理

对于正整数 a,b,ca, b, ca,b,c，它们可以作为三角形的三条边，当且仅当：  
a+b>c
a+c>b
b+c>a
均成立。如果我们将三条边进行升序排序，使它们满足 a≤b≤c，那么 a+c>b和b+c>a一定成立，我们只需要保证a+b>c

• 首先对数组排序。
• 固定最长的一条边，运用双指针扫描

1. 如果 nums[l] + nums[r] > nums[i]，同时说明 nums[l + 1] + nums[r] > nums[i], ..., nums[r - 1] + nums[r] > nums[i]，满足的条件的有 r - l 种，r 左移进入下一轮。
2. 如果 nums[l] + nums[r] <= nums[i]，l 右移进入下一轮。

• 枚举结束后，总和就是答案。

3、代码实现

class Solution
 {
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int ret=0,n=nums.size();
        for(int i=n-1;i>=2;i--)
        {
            int left=0,right=i-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[i])
                {
                    ret+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }

            }
        }
        return ret;


    }
};

（六） 查找总价格为目标值的两个商品

题目链接：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

1、题目描述：

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]
提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

2、算法原理：

使用左右指针，分别指向数组的首尾两个元素。
如果二者之和大于目标值，只能让右指针往左走。 因为左指针往右全部不满足。
如果二者之和小于目标值，只能让左指针往右走。 因为右指针往左全部不满足。
如果相等，直接返回。

3、代码实现：

class Solution 
{

public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        
            int left=0,right=price.size()-1;
            while(left<=right)
            {
              int sum=price[left]+price[right];
                if(sum<target)
                {
                    left++;
                }
                 if(sum>target)
                {
                    right--;
                }
               if(sum==target)
                {
                    return {price[left],price[right]};
                }
            }
        
        return{-1,-1};//保证每条路径都有返回值

    }
};

（七）三数之和

1、题目描述

题目链接：15. 三数之和 - 力扣（LeetCode）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

2、算法原理

先将 nums 排序，时间复杂度为 O(NlogN)

固定 333 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums)) 两端。

双指针 i , j 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3个元素都大于 000 ，在此固定指针 k 之后不可能再找到结果了。
当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
i，j 分设在数组索引 (k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：

• 当s < 0时，i += 1并跳过所有重复的nums[i]；
• 当s > 0时，j -= 1并跳过所有重复的nums[j]；
• 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。

图解如下：

3、代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> TreeDddZero;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            int left = i + 1, right = n - 1;
           // printf("left:%d right:%d i:%d\n", left, right, i);
            
            while (left <=right)
              
            {
                int sum = nums[left] + nums[right] + nums[i];
                if (sum < 0)
                {
                    left++;
                   // printf("left:%d   left+1:%d\n", left, left + 1);
                   
                }
                else if (sum > 0)
                {
                    right--;
                   //printf("right:%d   right+1:%d", right, right + 1);
                    
                }
                else
                {
                  //  printf("left:%d right:%d i:%d\n", left, right, i);
                    if (left == right) break;
                    TreeDddZero.push_back({ nums[i],nums[left],nums[right] });
                 
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1])
                    {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1])
                    {
                        right--;
                    }
                }

            }
            while (i<n-1 && nums[i] == nums[i + 1])
            {
                i++;
            }
        }

        return TreeDddZero;
    }
};

（八）四数之和

1、题目描述

题目链接：18. 四数之和 - 力扣（LeetCode）

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

2、算法原理

最朴素的方法是使用四重循环枚举所有的四元组，然后使用哈希表进行去重操作，得到不包含重复四元组的最终答案。假设数组的长度是 nnn，则该方法中，枚举的时间复杂度为 O(n4)，去重操作的时间复杂度和空间复杂度也很高，因此需要换一种思路。

为了避免枚举到重复四元组，则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素。

为了实现上述要求，可以对数组进行排序，并且在循环过程中遵循以下两点：

• 每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
• 同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素。

使用上述方法，可以避免枚举到重复四元组，但是由于仍使用四重循环，时间复杂度仍是 O(n4)。注意到数组已经被排序，因此可以使用双指针的方法去掉一重循环。

使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标 i 和 j，其中 i<j。初始时，左右指针分别指向下标 j+1和下标 n−1。每次计算四个数的和，并进行如下操作：

• 如果和等于 target\textit{target}target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数；
• 如果和小于 target\textit{target}target，则将左指针右移一位；
• 如果和大于 target\textit{target}target，则将右指针左移一位。

使用双指针枚举剩下的两个数的时间复杂度是 O(n)，因此总时间复杂度是 O(n3)，低于 O(n4)。

具体实现时，还可以进行一些剪枝操作：

• 在确定第一个数之后，如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target说明此时剩下的三个数无论取什么值，四数之和一定大于 target，因此退出第一重循环；
• 在确定第一个数之后，如果 nums[i]+nums[n−3]+nums[n−2]+nums[n−1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于 target，因此第一重循环直接进入下一轮，枚举 nums[i+1]；
• 在确定前两个数之后，如果 nums[i]+nums[j]+nums[j+1]+nums[j+2]>targett，说明此时剩下的两个数无论取什么值，四数之和一定大于 target，因此退出第二重循环；
• 在确定前两个数之后，如果 nums[i]+nums[j]+nums[n−2]+nums[n−1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮，枚举 nums[j+1]

3、代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> AddtoFour;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (n < 4)
            return AddtoFour;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int left = j + 1, right = n - 1;
                while (left < right)
                {
                    long long int aim =(long long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (aim < target) left++;
                    else if (aim > target) right--;
                    else
                    {
                        if (left >= right)
                            break;
                        AddtoFour.push_back({ nums[i],nums[j],nums[left],nums[right] });
                        left++, right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                while (j < n-1 && nums[j] == nums[j + 1]) j++;
            }
            while (i < n-1 && nums[i] == nums[i + 1]) i++;
        }
        return AddtoFour;

    }
};

 

最后，感谢大家的观看！