【优选算法】探索双指针之美（一）：初识双指针

前言:

双指针顾名思义就是用两个指针相互配合来解决问题的。这两个指针可以在同一个数组或链表上，也可以在不同的数据结构上。它们既可以同时移动，也可以一快一慢。

作用： 使用双指针可以提高效率，在一次遍历中就可以解决问题，避免了重复遍历和不必要的计算。

1.1 移动零

题目链接： 283.移动零 题目叙述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

解题思路： 双指针算法（利用数组下标充当指针）

1. 定义两个指针

cur:从左向右扫描数组，遍历数组。 dest:已经处理的区间内，非零元素的最后一个位置。

2. 两个指针将区间分为3部分

[0,dest]:非零元素 [dest+1,cur-1]:零元素 [cur,n-1]:待处理元素

3. 过程模拟

   ①让cur指向下标为0的位置

   ②让dest指向-1的位置（因为dest是非零元素的最后一个位置，刚开始时不知道第一个位置是否为非零元素）

   ③ 让cur进行扫描，cur会遇到两种情况：零元素和非零元素；     当遇到0元素时，cur++，就可以满足区间[dest+1,cur-1]为零元素     当遇到非零元素时，先让dest++,然后交换cur和dest位置上的值，cur++进行下一个数据的扫描

4. 代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur = 0,dest = -1;cur < nums.size();cur++)
        {
            if(nums[cur])//处理非零元素
            swap(nums[++dest],nums[cur]);
        }
    }
};

1.2 复写零

题目链接：1089.复写零 题目叙述： 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

解题思路： 先根据“异地”操作，然后优化成双指针下的“就地”操作

1.异地操作

    ① 定义一个cur指针，指向数组中的第一个元素     ②定义一个dest指针，指向开辟数组中最终的位置     ③当cur扫描时碰到非零元素，dest位置插入这个非零元素，cur++,dest++(两个指针同时向右挪动一位)

   ④ 当cur扫描时碰到零元素，dest位置插入0,dest向右再挪动一位插入0；cur++,dest++(两个指针同时向右挪动一位)    ⑤ [1,0,2,3,0,4,5,0] [1,0,0,2,3,0,0,4]

2.就地操作

当我们进行就地操作时，会发现从左向右操作时会覆盖掉数组中原来的数据，所以我们需要从右往左进行操作

从右往左进行操作时就需要首先找到cur指向的最后一个复写的数.

2.1先找到最后一个复写的数

    ①先判断cur位置的值，为0 ,dest移动2步；不为0，dest移动1步     ②移动dest     ③判断dest是否为最后一个位置     ④cur向下移动一位

2.2 处理边界情况

当我们找最后一个复写的数时会发现dest指向的位置会有两种情况

      ①判断是否dest > n-1       ② 若大于将n-1指向的位置赋0       ③ cur--,dest-=2

2.3 "从后向前"完成复写

   ①保证cur > 0    ②如果cur指向的位置不为零，将cur位置的值给dest，cur--,dest--    ③如果cur指向的位置为零,将dest位置的值赋0，dest++,再将dest位置的值赋为0；    ④cur--,dest--

3.代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //1.找到最后一个复写的数
        int cur = 0,dest = -1; int n = arr.size();
        while(cur < n)
        {
            if(arr[cur]) dest++;
            else dest+=2;
            if(dest >= n - 1) break;
            cur++;
        }
        //2.处理边界情况
        if(dest > n-1)
        {
            arr[n-1] = 0;
            cur--;
            dest-=2;
        }
        //"从前向后"完成复写
        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dest--] = arr[cur--];

            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0; 
                cur--;
            }
        }
    }
};

1.3 快乐数

题目链接：202.快乐数 题目叙述： 编写一个算法来判断一个数 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

解法： 快慢双指针

    ①定义快慢指针     ②慢指针每次向后移动一步，快指针每次向后移动两步     ③判断相遇时候的值

解题步骤： 1.定义一个函数获取每一位的数字的平方和 2.定义快慢指针 fast 指向第二个数, slow 指向第一个数 3.让slow 走一步，fast 走两步，直到两个相遇为止 4. 判断相遇位置的值

代码实现：

class Solution
{
public:
    int Sum(int n)//返回n这个数每一位上的平方和
    {
        int sum = 0;
        while(n)
        {
            int t = n % 10;
            sum += t * t;
            n = n / 10;
        }
        return sum;
    }
    bool isHappy(int n)
    {
        int slow = n,fast = Sum(n);
        while(slow != fast)
        {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
        }
        return slow == 1;
    }
};

最后

以上三道题就是对双指针算法的初步应用，可以帮助我们初步了解并熟悉双指针算法，欲知后事如何，关注我请听下回分解