算法——双指针

双指针经常服务于需要一边遍历数组，一边对数组元素进行改动的题目，有些人也称双指针为快慢指针。

同时双指针只是一种思想，实际做题时并不一定会真的采用指针。

---

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

本题的思路，并非是着重于将0往后移，实际上是要将非0数按顺序往前移。

由题意，我们可以将数据分成两大类：0和非0，那么我们的两个指针，一个就去找0，一个就去找非0。

两个指针均从0下标开始，其中cur找0，dest找非0。cur找到0即停下，dest找到非0即停下。

这样，dest总会走在cur的前面，两者将数据进行交换，就可以将非0元素前移，0元素后移。直至dest走到数组末尾。

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

---

 快乐数

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2
输出：false

通过实例的分析，这个题目我们不难理解，值得提醒的是，无论这个数起始是多少，变化了多少次，他最终都一定会进入循环，比如示例2，就会在4这个数字进入死循环，这个我们不做讲解，感兴趣的小伙伴可以自己去尝试分析解惑。

还有一点要注意的是，实际上当数最后变为1时，如果在进行运算，是一直以1在进行循环。

所以这道题的关键解法就在于，找到循环的数字，并判断是否为1。

 不知道小伙伴们还记不记得，在链表阶段，有一种循环链表的存在：

 其中，我们就是通过使用快慢指针的方法，来找到这个循环的入口，也就是本题要找的快乐数。

让慢指针每次走一步，快指针每次走两步，二者相等之时，即为在入口处相遇。

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

因为要经常进行运算，所以我们直接将其封装为函数方便调用。

然后我们就让slow从n开始，fast从n运算后的数开始，进行循环判断，循环结束即两者相等，再判断此时值是否为1，即可完成本题的解答。

---

查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

这个题可以说是足够简单了，对于暴力解法来说，只需要两层for循环去依次尝试两个商品的和是否等于目标值即可，但是这样的算法复杂度为0（n^2）。

那么是否可以有更加高效的方法呢？没错，就是双指针。

 题目明确给出，数组里的值已经是升序了（如果不是升序，我们可以利用排序使其变为升序），所以我们可以从两头出发，left指向最小值，right指向最大值，当两者的和大于目标值时，right--去找较小的值，反之让left++去找更大的值，直至两者的和等于目标值，或者不存在两个商品的和等于目标值为止。

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0;
        int right = price.size() - 1;
        int sum = 0;
        vector<int> v;
        while(left < right)
        {
            sum = price[left] + price[right];
            if(sum > target)
                right--;
            else if(sum < target)
                left++;
            else
            {
                v.push_back(price[left]);
                v.push_back(price[right]);
                break;
            }
        }
        return v;
    }
};

---

总结

不难看出，双指针算法最适用的场景即为线性表这样的数据结构类型，通过分析出问题的关键点，然后利用双指针，要么均从头开始，要么均从尾开始，要么一头一尾，逐步去解决问题。

关于双指针就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！