算法：双指针系列（一）

一、移动零

点击跳往题目

（一）题目分析

将数组分为三个区域（已遍历非零区， 已遍历零区，未遍历区），用两个指针来维护这三个区域。

（二）代码展示

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

二、复写零

（一）题目分析

这道题目中，也是采取双指针进行复写。我们可以开辟一段新空间复写比较简单，题目要求在原生空间复写。如果此时直接使用双指针会导致数组空间覆盖，可以先用双指针遍历找到复写的最后一个元素，反向复写，这样就不会出现问题。

（二）代码展示

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

三、快乐数

（一）题目分析

我们将这道题可以与链表的判环问题结合起来，要么存在循环，要么这个数就是快乐数。
只需要创建一个getNext 函数即可。

（二）代码展示

class Solution {
public:int getNext(int val) {int ret = 0;while (val > 0) {int temp = val % 10;ret = temp * temp + ret;val /= 10;}return ret;}bool isHappy(int n) {int fast = getNext(n), slow = n;while (fast != 1 && fast != slow) {fast = getNext(getNext(fast));slow = getNext(slow);}return fast == 1;}
};

（四）总结

涉及到元素的移动，数组的分区，亦或是判断是否有环（追击问题），双指针是不错的选择。