> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握双指针，并且能把下面的题目做出
> 毒鸡汤：人生就像一场马拉松比赛，不是看谁跑得最快，而是看谁坚持到最后。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考。
而今天我们的板块是双指针问题。
⭐知识讲解
双指针有两种形式，一种是对撞指针，另一种是左右指针（快慢指针）。
对撞指针：
- 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循 环）
快慢指针：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
⭐经典题型
🌙topic-->1
题目原型：
题目分析：
题目说的是，把一个数组含有0的数字甩到数组末尾，但不改变原数组顺序。
讲解算法原理：
编写代码：
class Solution { public: void moveZeroes(vector<int>& nums) { //两个指针 int cur = 0; int dest = -1; for(int i = 0;i < nums.size();i++) { //如果遇到0就交换 if(nums[cur] != 0) { swap(nums[++dest],nums[cur]); } //cur加加 cur++; } } };
🌙topic-->2
题目原型：
题目分析：
题目说，数组有0就再复写一遍，但是不能超过数组原来的长度。
讲解算法原理：
编写代码：
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 = top + 2; } else { top++; } } // 处理边界情况 int j = n - 1; if(top == n + 1) { arr[j] = 0; j--; i--; } // 开始出栈 while(j >= 0) { arr[j] = arr[i]; j--; // 如果i下标为0就让j再赋值一遍 if(arr[i] == 0) { arr[j] = arr[i]; j--; } i--; } } };
🌙topic-->3
题目原型：
题目分析：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
讲解算法原理：
编写代码：
class Solution { public: // 返回每一次剥离的结果 int bitSquareSum(int n) { int sum = 0; while(n > 0) { int t = n % 10; sum = sum + t*t; n = n / 10; } return sum; } bool isHappy(int n) { // 定义两个快慢指针 int fast = bitSquareSum(n); int slow = n; // 让快指针走2步，慢指针走1步 while(fast != slow) { fast = bitSquareSum(bitSquareSum(fast)); slow = bitSquareSum(slow); } return slow == 1; } };
🌙topic-->4
题目原型：.
题目分析：
求容量的最大能存水，用最小的柱高（y）乘以容量的宽（x）。
讲解算法原理：
编写代码：
class Solution { public: int maxArea(vector<int>& height) { // 定义左右指针 int left = 0; int right = height.size() - 1; // 定义最大容量v int 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; } };
🌙topic-->5
题目原型：
题目分析：
在数组中找三个数看看有多少个可以组成三角形。
讲解算法原理：
编写代码：
class Solution { public: int triangleNumber(vector<int>& nums) { // 先让数组排升序 sort(nums.begin(),nums.end()); // 利用双指针来解决问题 int count = 0; int n = nums.size(); for(int i = n - 1;i >=2;i--)// 固定最大值 { // 定义双指针 int left = 0; int right = i - 1; while(left < right) { if(nums[left] + nums[right] > nums[i]) { count = count + right - left; right--; } else { left++; } } } return count; } };
🌙topic-->6
题目原型：
题目分析：
在数组中找两个数之和能等于target就返回这两个数。
讲解算法原理：
编写代码：
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { // 定义双指针 int left = 0; int right = price.size() - 1; // 循环 while(left < right) { int sum = price[left] + price[right]; if(sum > target) right--; else if(sum < target) left++; else return {price[left],price[right]}; } // 如果没有的话就返回空 return {}; } };
🌙topic-->7
题目原型：
题目分析：
在数组中找三个数之和是否为0，如果为0就返回这三个数，并且不能重复。
讲解算法原理：
编写代码：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // 定义数组 vector<vector<int>> ret; // 让数组升序 sort(nums.begin(),nums.end()); int n = nums.size(); // 定住一个数字，利用双指针法 for(int i = 0;i < n;) { // 优化 if(nums[i] > 0) break; // 定义双指针 int left = i + 1; int right = n - 1; // 标记 int target = -nums[i]; while(left < right) { int sum = nums[left] + nums[right]; if(sum > target) right--; else if(sum < target) left++; else { // 尾插 ret.push_back({nums[i],nums[left],nums[right]}); right--,left++; // 去重left和right while(left < right && nums[left] == nums[left-1]) left++; while(left < right && nums[right] == nums[right+1]) right--; } } // 去重I i++; while(i < n && nums[i] == nums[i-1]) i++; } return ret; } };
🌙topic-->8
题目原型：
题目分析：
在数组中找四个数之和是否为0，如果为0就返回这四个数，并且不能重复。
讲解算法原理：
这里就不讲解原理了，这里和第 7 道题相似的。
编写代码：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { // 定义数组 vector<vector<int>> ret; // 让数组升序 sort(nums.begin(),nums.end()); // 利用双指针 int n = nums.size(); for(int i = 0;i < n;) { // 使用三数之和的方法 for(int j = i + 1;j < n;) { // 定义双指针 int left = j + 1; int right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; // 循环 while(left < right) { int sum = nums[left] + nums[right]; if(sum < aim) left++; else if(sum > aim) right--; else { // 尾插 ret.push_back({nums[i],nums[j],nums[left++],nums[right--]}); // 去重left while(left < right && nums[left] == nums[left - 1]) left++; while(left < right && nums[right] == nums[right + 1]) right--; } } j++; // 去重j while(j < n && nums[j] == nums[j - 1]) j++; } i++; // 去重i while(i < n && nums[i] == nums[i - 1]) i++; } return ret; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
