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

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

移动零

给定一个数组 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& 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 twoSum(vector& price, int target) {         int left = 0;         int right = price.size() - 1;         int sum = 0;         vector 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;     } };

总结

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

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