刷题训练之双指针问题

• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循 环）

快慢指针：

• 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

⭐经典题型

🌙topic-->1

题目原型：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目分析：

题目说的是，把一个数组含有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

题目原型：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目分析：

题目说，数组有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

题目原型：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目分析：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 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

题目原型：. - 力扣（LeetCode）

题目分析：

求容量的最大能存水，用最小的柱高（y）乘以容量的宽（x）。

讲解算法原理：

编写代码：

class Solution {
public:int maxArea(vector<int>& height) {// 定义左右指针int left = 0;int right = height.size() - 1;// 定义最大容量vint 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

题目原型：. - 力扣（LeetCode）

题目分析：

在数组中找三个数看看有多少个可以组成三角形。

讲解算法原理：

编写代码：

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

题目原型：. - 力扣（LeetCode）

题目分析：

在数组中找两个数之和能等于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++;elsereturn {price[left],price[right]};}// 如果没有的话就返回空return {};}
};

🌙topic-->7

题目原型：. - 力扣（LeetCode）

题目分析：

在数组中找三个数之和是否为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和rightwhile(left < right && nums[left] == nums[left-1])left++;while(left < right && nums[right] == nums[right+1])right--;                   }}// 去重Ii++;while(i < n && nums[i] == nums[i-1])i++;}return ret;}
};

 🌙topic-->8

题目原型：. - 力扣（LeetCode）

题目分析：

在数组中找四个数之和是否为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--]});// 去重leftwhile(left < right && nums[left] == nums[left - 1])left++;while(left < right && nums[right] == nums[right + 1])right--;}}j++;// 去重jwhile(j < n && nums[j] == nums[j - 1])j++;}i++;// 去重iwhile(i < n && nums[i] == nums[i - 1])i++;}return ret;}
};

 🌟结束语

       今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。