OJ算法练习（双指针篇）

1、双指针介绍

双指针顾名思义就是有两个指针，常见的双指针算法有以下两种，下面只是介绍常见的，不代表下面的题目全部都是使用这两种。

1.1 对撞指针

对撞指针就是让一个left指针在数据的左边，然后让一个right指针在数据的最右边，然后让他们往中间靠，当left指针走到right指针的右边时停止走动。（简单点总结就是：从两边往中间靠）

1.2 快慢指针

快慢指针其实就是两个指针走的速度不一样，慢指针走一步，快指针走两步，这个非常有用，当我们想找到中间那个数据的时候就可以使用快慢指针实现，举个例子，例如长度为x的路，快指针走完x的路时，慢指针才走了1/2 x，因为快指针的每次都比慢指针走多一步。

2、双指针OJ题

2.1 移动0

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

题目介绍如下图见：

总结就是把一个数组中的0全部挪到后面去，而且还要保证非0元素的相对位置没有发生改变。

算法思路：

我们可以创建两个指针，一个cur，一个dest，cur用来遍历数组的数据，dest用来记录非零数据区域内的最后一个数据。然后根据cur在遍历数组时碰到0或者非0元素时进行分类处理即可。

dest本质上就是为了实现一个区间[0, dest]区域内的数据都是非0元素，[dest+1, cur-1]的元素全部都是0。

具体实现过程：

cur初始化为0，dest初始化为-1，因为我们不知道第一个元素是否为0，所以先让dest为-1，然后cur遍历数组，如果cur位置的数据不等于0，那就让dest+1的数据和cur位置的数据交换然后往前走，如果cur位置的数据为0，那就只让cur往前走。

实现代码如下：

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int dest = -1;
        int cur = 0;
        while(cur<nums.size())
        {
            if(nums[cur]!=0)
            {
                swap(nums[++dest], nums[cur]);
            }
            cur++;
        }
    }
};

2.2 复写0

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

题目介绍如下：

总结题目：就是把数组内的0写多一遍，举个例子，例如数组内的数据为1、0、3、2，那么就需要对0进行复写即1、0、0、3、2。看到题目的时候我们就肯定能想到在原数组内对数据进行复写太麻烦，可能会出现把某些数据覆盖掉的情况，所以想到可以开多一个数据进行实现，单题目说了要就地进行修改，那么这里我们需要用的双指针算法进行实现。

算法思路：

先用快慢指针找到复写数的最后一个位置，然后再通过cur和dest从后往前进行复写操作即可。

具体实现过程：

从前面进行复写会出现数据覆盖，那么我们就从后面进行复写。进行从后往前复写，我们需要知道我们复写最后一个数据的位置在哪里，我们看图上的示例一发现最后一个是4，那么我们该怎么知道是4呢？这时候我们就需要使用双指针，即cur遍历数组，如果cur==0，dest+=2，如果cur等于非0的数就让dest++，这样就能为复写的数字分配位置了。如下动图所示为找到复写位置：

我们发现dest这样子走的话最终也保证了题目给的条件“不能超过原数组的长度”，实质上cur为0的时候dest走两 步实质上就是为了给0复写流出位置，然后我们再从后往前进行复写即可完成，操作为：cur和dest往前走，cur不能超出0位置，如果cur为0，那么就让dest赋值为0，然后dest--然后再赋值为0，因为是0的时候需要复写两次，非0则直接arr[dest] = arr[cur]然后两个往后走。

注意！还有一种特殊情况就是如果说倒数第二个数为0的话，在双指针找复写后的最后一个位置时dest会出现越界情况。遇到这种情况我们加多个判断条件即可，如果出现越界那肯定是最后一个复写数为0,。

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


        while(cur>=0)
        {
            if(dest>n-1)
            {
                arr[n-1] = 0;
                dest-=2;
                cur--;
            }
            if(arr[cur]!=0)
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                int k = 2;
                while(k>0)
                {
                    arr[dest--] = 0;
                    k--;
                }
                cur--;
            }
        }
    }
};

2.3 快乐数

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

题目介绍如下图见：

总结题目意思：输入n，然后取出他的每一位平方然后进行相加，一直循环，如果最后的结果为1，那就是快乐数，如果始终不为1，那就是进入死循环了。而这个死循环就是会出现已经出现过的情况，如下图，这是不是就很像判断链表是否有环那道题目了，这就是我们的解题思路。

算法思路：

上面我们分析得到，类似判断链表是否有环的那道题，而解决那道题用到的就是快慢指针，因为如果链表有环的话，最终快指针会追上慢指针，如果没法理解清楚的话我们可以想象两个人跑步，跑得快的人一开始就比慢的人走得快，那么过一段时间后快的人又会与慢的人相遇，而我们的判断条件就是如果fast!=slow的话就进入循环去计算他们每一位数字的平方 的和是否为1即可。（注意：这里的快慢指针遍历不是字面上的遍历，而是通过计算得到那个数例如上面那张图的从2-->4，slow指针只进行一次计算，而fast指针进行两次计算即2-->4-->16）

具体实现过程：

使用快慢指针进行遍历，在遍历过程中如果快指针不等于慢指针期间，就计算当前指针下的数的每一位平方然后相加是否等于1，如果等于1跳出循环，不等于1，则说明是无限循环，且fast==slow，那就返回false。（注意：这里的快慢指针遍历不是字面上的遍历，而是通过计算得到那个数例如上面那张图的从2-->4，slow指针只进行一次计算，而fast指针进行两次计算即2-->4-->16）

代码实现如下：

class Solution {
public:
    int caculate(int n) {
        int total = 0;
        while (n) 
        {
            int temp = n % 10;
            total += temp * temp;
            n = n/10;
        }
        return total;
    }
    bool isHappy(int n) {
        int slow = n;
        int fast = caculate(n);
        while (fast != slow) {
            slow = caculate(slow);
            fast = caculate(caculate(fast));
        }
        if (fast == 1) 
        {
            return true;
        } else 
        {
            return false;
        }
    }
};

2.4 盛最多水的容器

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

题目介绍如下：

总结题意：就是我们需要找到一个能盛最多水的容器，也就是他的长和高的乘积最大的值，如下图，然后要注意的就是盛水就和水桶效应那样，不是找最长的高，而是最低的高，因为水量是由最矮的那块木板决定的，这样我们就能知道，我们需要找length * h最大的值。

算法思路：

通过指针碰撞决定，首先比较数组内left位置和right位置的值，找出两者最小值然后乘以length（right-left），如果arr[left] < arr[right]的值，那么就让left++，然后定义一个MaxNum进行记录他们的值：arr[left] * (right-left)。

实现思路：

首先定义left指向最左边，right指向数组最右边，然后定义一个length = right-left，用length记录如上图的长，然后再定义一个MaxNum，MaxNum就是用来存储length * h的值，但是这时候我们不知道用什么来初始化MaxNum，那么我们就可以选择当前left和right所处的位置的最小的那块木板的长度来乘以length进行初始化MaxNum。

初始化完MaxNum后，就可以对left和right内的值进行一一查找，我们需要找到大于MaxNum的值来更新MaxNum，因为用MaxNum来存储盛最多水的容器的容积

然后我们来列出个式子，V = h* length，由此可知v、length和V都是成正比关系，那么我们想要V变大，就需要让h和length变大，但是length是不可能变大的，因为两边的指针往中间靠 然后找数据，所以length只能是变小，那么我们就需要让h变大，所以我们需要让小的一边移动，如果height[left]小于height[right]的话，那就需要让left++，在此同时我们还需要更新h，且h为最小值，h = height[left]，然后h * length和MaxNum判断谁大，然后更新MaxNum；如果height[left]大于height[right]的话，那就需要让right--，在此同时我们还需要更新h，且h为最小值，h = height[right]，然后h*length和MaxNum判断谁大，然后更新MaxNum。

如下代码所示：

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0;
        int right = height.size()-1;
        int length = right - left;

        //取小来初始化
        int MaxNum;
        if(height[left] > height[right])
        {
            MaxNum = height[right--] * length;
        }
        else
        {
            MaxNum = height[left++] * length;
        }

        while(left<right)
        {
            length = right - left;
            int h = height[left];
            if(height[left]>height[right])
            {
                h = height[right--];
            }
            else
            {
                h = height[left++];
            }
            // if(max<(W*h))
            // {
            //     max = (W*h);
            // }
            MaxNum = max(MaxNum, (length*h));
        }
        return MaxNum;
    }
};

2.5 有效三角形的个数

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

题目介绍如下：

总结题目：我们小学的问题，就是判断给的三个数是否能构成三角形，判断条件是：两边之和大于第三边，a+b>c，b+c>a，a+c>b。

算法思路：

使用三个指针进行遍历数组，然后判断三个指针位置的值是否符合构成三角形的条件，定义一个count变量，如果符合则count++。

实现思路：

如果我们按两边之和大于第三边，a+b>c，b+c>a，a+c>b,这些条件判断的话太麻烦了，可能会超时，那么我们就可以尝试找一下特殊情况，假如说c为最大值，那么我们要符合两边之和大于第三遍，这个条件的话是不是就只需要让a+b>c即可，因为c为最大值，c加哪一个都肯定大于另一个值。所以我们可以让数组先排序，然后让c为数组的最后一个元素即最大值，然后判断[0,c)内的值，通过指针对撞left = 0,right = c-1来遍历[0, c-1]里面的值相加是否大于c，如果arr[left]+arr[right]小于arr[c]，那就说明需要一个值变大，就只能让left++，如果arr[left]+arr[right]要是大于arr[c]的值的话，那就说明right-left区域内的值都肯定大于c（解释：因为数组是有序的，arr[left]的值在[left, right]内肯定是最小的，那最小的加arr[right]都大于arr[c]，那么这个范围内的值加arr[right]都肯定大于arr[c]）

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        //首先是对数组进行排序
        sort(nums.begin(), nums.end());
        //排好序了就开始循环
        int MaxC = nums.size()-1;
        int left = 0;
        int right = MaxC-1;
        int count = 0;
        while(MaxC>=2)
        {
            //开始判断a+b的结果
            while(left!=right)
            {
                if(nums[left]+nums[right]<=nums[MaxC])
                {
                    left++;
                }
                else
                {
                    count += right-left;
                    right--;
                }
            }
            MaxC--;
            right = MaxC-1;
            left = 0;
        }
        return count;
    }
    
};

注意：每次我们都需要更新c的值。

2.6 和为s的两个数字

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

题目介绍：

总结题意：就是找两个数字的和为target的值。看到这我们可能就想到了用两个for循环进行遍历，但这样可能会超时，所以我们可以使用双指针算法。

算法思路：

定义一个left和right，在left和right区域内找两个值相加等于target的。

实现思路：

定义两个指针，left和right，left指向数组首位元素，right指向数组末尾元素，然后在[left, right]这个区域内找两个数字相加等于target，如果arr[left]+arr[right]小于target，那就需要让left++，注意！给的数组是升序的，所以left的位置一定是最小值，arr[left]+arr[right] <target，只能让left++，如果arr[left]+arr[right]>target，那就只能让right--，right处肯定是最大值，最小加最大大于target，那就只能让arr[left]+arr[right]减小，因为我们找的是相等的值。

实现代码如下：

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 {-4941,-1};
    }
};

最后一段代码是照顾编译器。

2.7 三数之和

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

题目介绍如下：

总结题意：找三个数相加的和为0，且不能出现重复的一组数据，顺序表不同也不行。这个和我们上面的和为s的两个数的算法很相似，只不过在这里我们需要做一个判断就是跳过相同的数字。

首先我们看，他要的是三个数相加的和为0，那我们可以这样思考，就是固定一个数Fixed为首位元素的值，然后计算[Fixed+1, n-1]区域内的数相加等于-Fixed，因为要实现三个数相加的和为0，那么就让两个数相加的和等于另一个数的相反数即可。

算法思路：

固定一个值Fixed，然后找这个固定值前面的区域内是否有值等于固定值的相反数，并且在Fixed到数组最后一个元素区域内定义两个指针left和right，然后对这个区域内的数据进行判断是否符合条件，和上面几乎类似，但这里面添加了新条件就是不能有相同的值，如果相同则需要接着往前或者往后走，直到找到不是相同的值为止。

实现思路：

首先对数组内的元素进行排序，这样我们就可以按照前面的如果arr[left]+arr[right]的值小于目标值，那就让left++，right保持不动，如果arr[left]+arr[right]的值大于目标值，那就让right--，保持left不动；然后固定一个值Fixed从首元素进行遍历整个数组，然后left和right位于[Fixed+1, n-1]内，即left = Fixed+1, right = n-1，然后遍历[left, right]区域内的数据相加的值和arr[Fixed]的值进行比较，小就让left++，大就让right--，如果相等后就让left和right同是往前移动一个位置，left++,right--，然后还要判断arr[left+1]的值是否等于arr[left]的值，如果等于就接着往前走，因为我们不能有相同的值，right也一样，一直遍历left==right的时候或者left>right的时候停止循环，然后出循环对Fixed进行修改，因为Fixed也要遍历完整个数组，然后就让Fixed++，最后也要判断arr[Fixed+1]是否等于arr[Fixed]的值，如果等于就还要让Fixed++，直到不等于。

实现代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> temp;
        sort(nums.begin(), nums.end());
        int Fixed = 0;
        int n = nums.size();
        while(Fixed<n)
        {
            int left = Fixed+1;
            int right = n-1;
            int target = -nums[Fixed];
            while(left<right)
            {
                int sum = nums[left]+nums[right];
                if(sum<target)
                {
                    left++;
                }
                else if(sum>target)
                {
                    right--;
                }
                else
                {
                    temp.push_back({nums[Fixed], nums[left], nums[right]});
                    left++;
                    right--;
                    while(left<right&&nums[left]==nums[left-1])
                    {
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right+1])
                    {
                        right--;
                    }
                }
            }
            Fixed++;
            while(Fixed<n&&nums[Fixed]==nums[Fixed-1])
            {
                Fixed++;
            }
        }
        return temp;
    }
};

2.8 四数之和

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

题目介绍如下：

总结题目：和上面几乎类似，只是加多一个循环而已，这里就不细讲了。直接上代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> vv;
        sort(nums.begin(), nums.end());
        int begin = 0;
        int n = nums.size();
        while(begin < n)
        {
            int end = begin+1;
            while(end < n)
            {
                int left = end+1;
                int right = n-1;
                long long aim = (long long)target - nums[begin]-nums[end];
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum < aim)
                    {
                        left++;
                    }
                    else if(sum > aim)
                    {
                        right--;
                    }
                    else
                    {
                        vv.push_back({nums[begin], nums[left], nums[right], nums[end]});
                        //入完数据就让left++,right--，然后还要判断一下前面是否有相同的值，有的话就跳过
                        left++;
                        right--;
                        while(left < right && nums[left]==nums[left-1])
                        {
                            left++;
                        }
                        while(left < right && nums[right]==nums[right+1])
                        {
                            right--;
                        }
                    }
                }
                end++;
                while(end < n&& nums[end]==nums[end-1])
                {
                    end++;
                }
            }
            begin++;
            while(begin < n&& nums[begin]==nums[begin-1])
            {
                begin++;
            }
        }
        return vv;
    }
};

END!