在快速排序或者是其他和数组有关的题目中，有很经典的一类题目是关于数组划分的，数组划分就是把数组按照一定的规则划分为不同的区间，使得达到某种目的
首先先看实现的原理是什么
实现原理
两个指针的作用？
cur：从左向右扫描数组，遍历数组
dest：已处理的区间内，非零元素的最后一个位置
数组划分就是把数组划分成三个区间：
[0，dest]、[dest+1，cur-1]、[cur，n-1]
而这三个区间就对应到了题目要求的区间，假设现在有这样的题目
那经过区间划分，就可以把[0，dest]划分为非0的区域，[dest+1，cur-1]划分为只有0的区间，而剩下的就是待处理的区间
实现思路
有了上面的理论基础，实现思路就简单多了：
我们让cur从前向后遍历，如果cur遇到0元素，就让cur++，因为cur相当于是一个用来探路的指针，而dest的作用就是用来进行区间的划分，于是根据这个原理，当cur遇到了非0的元素时，就让dest++再让cur和dest这两个位置的元素进行一次交换，交换后的结果就达到了，把非0元素交换到前面，0元素换到后面的结果
技巧
永远让dest初始值为-1，cur的初始值为0，并且让cur最后更变值，可以有效处理掉很多越界问题
典型例题
先看几个简单的题目熟悉这个算法的思路：
移动0
void moveZeroes(vector<int>& nums) { int cur=0; int dest=-1; while(cur<nums.size()) { if(nums[cur]==0) { cur++; } else { dest++; swap(nums[dest],nums[cur]); cur++; } } }
看上述代码，就严格执行了刚才代码的思路
- 如果
cur遇到0元素，就让cur++ - 当
cur遇到了非0的元素时，就让dest++再让cur和dest这两个位置的元素进行一次交换
复写0
既然通篇介绍的主要是双指针算法，那这个题也要使用双指针的基本原理
如果此题可以创建多个数组，那么创建一个数组，上面一个指针控制原数组，下面控制新数组，如果是0就填入两个0，如果不是0就填入该数字，到达对应数量就不再进行写入数据
但这里要求不能够使用额外的空间，因此就要把异地的双指针变成原地双指针
那原地双指针如何实现？
首先，原地的双指针问题在于，如果从前向后遍历，当遍历到的数字是0，写入两个0后，原来的数据就被覆盖掉了，这样就会一直进行0的循环，因此解决方案就是从后向前遍历
那么接下来思考如何遍历？一个从最后开始，那另外一个？显然，这是下一个需要解决的问题，另外一个部分应该从哪里开始
通过这里画图也能看出，cur的位置其实就是复制结束后的位置，那么这个位置的寻找过程就是下一步要进行的问题
cur应该如何寻找？其实又可以演化为双指针的问题，从开始找，当遇到0就向后走两次，遇到非0就走一次，那么这样就可以找到cur
这样的思路是没有问题的，但是也有特殊情况，如果最后元素是0，那dest向后走两步不就越界了吗？因此这里也需要对边界做特殊处理，如果边界为0，那么就让最后输出的dest和cur向前一步走即可避免越界的情况出现
class Solution { public: void duplicateZeros(vector<int>& arr) { int cur=0,dest=-1,n=arr.size(); while(cur<n) { if(arr[cur]==0) { dest+=2; } else { dest++; } if(dest>=n-1) { break; } cur++; } if(dest==n) { arr[n-1]=0; cur--; dest-=2; } while(cur>=0) { if(arr[cur]==0) { arr[dest--]=arr[cur]; arr[dest--]=arr[cur--]; } else { arr[dest--]=arr[cur--]; } } } };
快乐数
这个题思路也很奇特，先模拟一下实现的流程：
情景1：
情景2：
此时对题意就有了基本了解，那么这个图其实和链表中的环形链表很相似，我们其实就可以把他抽象成一个环形链表的相遇问题，当相遇的时候，如果对应的值不是1，那么就证明这里并不是快乐数，相反就是快乐数
因此这个题就很好解决了，本质上这个原理和环形链表的快慢指针的过程是一样的
class Solution { public: int CalRes(int num) { int res = 0; while (num) { res += (num % 10) * (num % 10); num = num / 10; } return res; } bool isHappy(int n) { int num = n; int slow = CalRes(num); int fast = CalRes(CalRes(num)); while (slow != fast) { slow = CalRes(slow); fast = CalRes(CalRes(fast)); } if (fast == 1) { return true; } else { return false; } } };
盛最多水的容器
本题设计也很巧妙，但依旧是利用双指针来解决，知道了双指针的解决原理后解决并非难事
一个从左走 一个从右走 根据木桶效应，计算出结果后要舍弃小的部分，继续向内遍历，使得最终时间复杂度控制在O(N)内
class Solution { public: int maxArea(vector<int>& height) { int left = 0; int right = height.size() - 1; int v = 0; int max = 0; while (left < right) { v = min(height[left], height[right]) * (right - left); if (v > max) { max = v; } if (height[left] < height[right]) { left++; } else { right--; } } return max; } };
有效三角形的个数
看到这个题，第一思路是直接暴力枚举三次for循环，直接找，但最后是通过不了的，时间复杂度过高了，因此这里还是使用双指针的解法，但是要利用单调性进行解决
首先，对于三个数字我们要进行判断的时候，如果这个数字是单调排序的，比如这里是升序排序，那么只需要判断前两个数相加的和大于第三个数即可，因此根据这个原理，我们就可以采取下面的思维方式
依据单调性采用双指针解决问题
这个算法的思路就是，先固定右边最大的数字作为最大的数，倒数第二大的数字为right，左边的数为left
如果此时left+right>固定，那么此时left右边的数同样符合条件，那么只需要right--即可
如果此时left+right<固定，那么此时left后面的数也不符合要求，就让left++
循环结束后，再通过挪动右边的数进行循环，这样时间复杂度在O(N^2)的基础上就解决了这个问题
class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); int cut=0; for(int max=nums.size()-1;max>=2;max--) { int left=0,right=max-1; while(left<right) { if(nums[left]+nums[right]>nums[max]) { cut+=right-left; right--; } else { left++; } } } return cut; } };
三数之和
此题难度在于代码实现的细节处理和去重的问题上
代码思路有两数之和的思路铺垫，整体难度不大，控制住其中一个进行另外两个数据的相加即可，但在边界的处理上需要进行一些操作
最后是去重的操作，去重的操作是很重要的一步，细节很多，要处理区间内的去重和区间外单独的去重
vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> v; // 排序 sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();) { // 优化 if(nums[i]>0) { break; } int left=i+1,right=nums.size()-1; while(left<right) { if(nums[left]+nums[right]+nums[i]>0) { right--; } else if(nums[left]+nums[right]+nums[i]<0) { left++; } else { v.push_back({nums[i],nums[left],nums[right]}); left++; right--; // 去重1 while(left<right && nums[left]==nums[left-1]) { left++; } while(left<right && nums[right]==nums[right+1]) { right--; } } } // 去重2 i++; while(i<nums.size() && nums[i]==nums[i-1]) { i++; } } return v; }
四数之和
代码思路和三数之和基本相同，注意long long问题即可
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> v; // 排序 sort(nums.begin(),nums.end()); // 控制第一个数 for(int i=0;i<nums.size();) { // 控制第二个数 for(int j=i+1;j<nums.size();) { // 在区间内找 int left=j+1,right=nums.size()-1; while(left<right) { long long tmp=(long long)nums[i]+nums[j]+nums[left]+nums[right]; if(tmp>target) { right--; } else if(tmp<target) { left++; } else { v.push_back({nums[i],nums[j],nums[left],nums[right]}); left++; right--; // 去重 while(left<right && nums[left]==nums[left-1]) { left++; } while(left<right && nums[right]==nums[right+1]) { right--; } } } // 对固定数去重 j++; while(j<nums.size() && nums[j]==nums[j-1]) { j++; } } i++; while(i<nums.size() && nums[i]==nums[i-1]) { i++; } } return v; } };
总结
双指针问题是入门算法题，但却有很大的使用场景，具体来说，当要进行数组划分和数组分块的时候，可以选择先进行排序，进行有序数组
对于有序数组来说，利用单调性解决问题是常见的手段，在实际应用题目中有很大的利用价值
