初识算法 · 双指针（1）
目录
前言：
双指针算法
题目一：
编辑
题目二:
前言：
本文作为算法部分的第一篇文章，自然是少不了简单叭叭两句，对于算法部分，多刷是少不了，我们刷题从暴力过度到算法解法，自然是一个很痛苦的过程，而算法本身的思考是很重要的，所以算法部分的介绍大多都是通过题目直接介绍，以题目来灌注算法知识，因为每人对于算法的接受程度有限，每篇大多都是两题左右，对于难题部分，大多时候只会出一道，并且均以leetcode作为题目来源，本文都会以最优质的解法来介绍不同的算法，通过三个部分来解决题目，题目解析，算法原理，算法编写。
双指针算法
题目一：
样例为：
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]
题目解析：
给定一个数组，移动0到末尾，不必考虑0的相对顺序，但是要保持非零的相对顺序。
如果不使用双指针，有很多解法，比如我们可以将所有的非零元素移动到最开始，但是移动一次，就需要遍历一次，时间复杂度是接近于O(N^2)的，因为不能数组，这是一种暴力解法，那么我们如何使用双指针呢？
算法原理：
通过使用双指针，将数组划分为三个区域：
[0,dest]划分为非零元素的区域，[dest,cur]划分为0元素的区域，[cur,end]划分为还没有遍历的区域。既然是使用双指针算法，我们自然需要定义两个“指针”，可是这里实际上不是指针，这里我们需要对双指针有一个形象的认识，双指针并不是真正的用指针，它们代表的只是形象的指向两个元素而已，这里的指针可是是一个数，可以是数组，可以是任何能代替指向的东西。
这里是数组下标，所以定义两个下标是必不可少的。
然后就是进行划分区域，二者都是从0开始划分，dest我们不知道如何定义可以先不管，cur遍历数组，找到非零的元素，就给dest，那么怎么给呢？dest可以从-1开始，因为cur就是从0开始的，找到了非零元素，dest++进行交换，cur正常走即可。
算法编写：
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]);
}
}
};就过啦，可能算法代码出乎你想象的简单，习惯就好。
简单的分析一下时间复杂度吧，一次遍历，O(N)，如果暴力是平方，这优化的就很不错了。
题目链接：283. 移动零 - 力扣（LeetCode）
题目二:
样例为：
输入：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
题目解析：
题目名为快乐数，让我们看看题目有多快乐吧！
快乐数的定义为将一个数多次等于该数上的每一位数字的平方相加，如果经过多次变化，数字可以变为1，那么就是快乐数，但是如果是一直无线循环没有变成1，那么该数就不是快乐数。对于这种题目就没有暴力解法了，因为真要暴力的话很有可能套死循环出不去了。所以我们直接进入到算法原理部分。
算法原理：
我们不妨画图，看看变化是怎么个事儿：
对于19来说，经过了4次变化就到1，那么对于2来说，经过多次变化，出现了和第一次变化一样的值，4。
那么我们可不可以理解2在变化的时候出现了环，且数的变化出不了这个环，所以它不是快乐数，那么好像看起来也没啥啊，19也没有出现环，可是，如果我们换个角度，19变化的时候，是不是出现了一个环，环里面只有1呢？
这时候相信大部分人已经明了了，我们只需要判断环里面是不是1即可，即我们可以使用两个指针，一个走的快，一个走的慢，二者是一定相遇的，相遇的时候，看相遇的点是不是1就可以了。
那么就有第二个问题了，为什么一定会出现环呢？
这里要使用到的是我们之前未曾听闻的一个数学原理，鸽巢原理。
我们使用鸽巢原理来证明一定会出现环状：
这是Leetcode中告诉的n最大的取值，那么：
这是最大的取值，我们不妨这样，一共有10个数字，我们再大一点，10个9，也就是说，我们计算一下9999999999经过一次变化之后的取值，变化之后的取值是810，也就是说，变化之后最大的值一定不会超过810。不妨定义函数F(x)等于一次变化，那么一个数经过811变化，也就是产生了811个数，但是总的区间只有810，那么一定有一个数是重复的，这就是鸽巢原理的应用。
算法编写：
class Solution
{
public:
int _isHappy(int num)
{
int ans = 0,sum = 0;
while(num)
{
sum = num % 10;
ans = ans + sum * sum;
num /= 10;
}
return ans;
}
bool isHappy(int n)
{
int slow = n,fast = n;
while(1)
{
slow = _isHappy(slow);
fast = _isHappy(_isHappy(fast));
if(slow == fast)
{
if(slow == 1)
return true;
else
return false;
}
}
}
};一个函数，_ishappy对应函数F(x)，那么快慢指针，就是一个变化两次，一个变化一次，当它们相等的时候，判断即可，这里也应证了双指针的算法并不是真的使用指针，它更多的只是一种思想而已！！
今日算法到这里了，感谢阅读！