刷题训练之双指针问题

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

快慢指针：

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

?经典题型

🌙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;
        // 定义最大容量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

题目原型：. - 力扣（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++;
            else
                return {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和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

题目原型：. - 力扣（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--]});
                        // 去重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;
    }
};

?🌟结束语

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