优选算法的协作之舞：双指针专题(二)
专栏：算法
个人主页：手握风云
目录
一、算法例题
1.1. 复写零
题目要求我们要进行就地修改，并且函数不返回任何类型。我们先思考两个数组异地修改。我们同样是定义两个指针cur和dest。当cur指向非零元素时，dest直接照抄，然后统一向右移动一位；当cur指向零元素时，dest照抄两遍。
我们接着对异地操作进行优化，然后再思考就地操作。如果cur指向零元素时，就会把下一个元素给覆盖掉，导致后面都会被复写成零，所以两个指针从前向后完成复写操作是错的。那我们就换一种思路，从后向前完成复写。
由于题目要求不能超过原有数组的长度，所以我们首先要找到复写之后数组的最后一个元素。我们让cur指向非零元素，dest向右移动一位；如果cur指向零元素，dest向右移动两位。但此时还有一种特殊情况，如果复写之后最后一个元素为零，那么dest就会越界，所以我们还要单独处理一下边界，只需把倒数第二个元素直接复写成零，然后cur向前移动一位，dest向前移动两位。
完整代码实现：
class Solution { public void duplicateZeros(int[] arr) { int cur = 0,dest = -1,n = arr.length; //先找到最后一个需要复写的数 while(cur < n){ if(arr[cur] == 0){ dest+=2; }else{ dest+=1; } 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--]; }else{ arr[dest--] = 0; arr[dest--] = 0; cur--; } } } }1.2. 快乐数
我们先要明白快乐数的定义。通过上图所示，要判断一个数是否是快乐数，就是判断一个链表是否有环，且环是否为1。我们之前已经在链表章节讲过类似的题目。定义一个快指针和一个慢指针。快指针一次走两步，慢指针一次走一步，最终两个指针一定会相遇。也就是我们要判断相遇点是否为1。
class Solution { public int HappySum(int n){ int sum = 0; while(n != 0){ int t = n%10; sum += t*t; n/=10; } return sum; } public boolean isHappy(int n) { int slow = n; int fast = HappySum(n); while(slow != fast){ slow = HappySum(slow); fast = HappySum(HappySum(fast)); } return slow == 1; } }1.3. 三数之和
首先我们依然想到的是先排序，然后暴力枚举，利用三层for循环来判断三数之和是否为零，由于题目不要求输出的顺序和三元组的顺序，所以我们需要对三元组进行去重的操作，那么此时的时间复杂度就是
。
接着我们对解法进行优化，对于有序数组，我们可以想到二分查找或者是双指针。我们先固定第一个元素，然后从剩余的区间里面查找两数之和是否为被固定数字的相反数。查找两数之和，我们这里就不再多说。
接下来是去重操作。我们先对三元子数组进行去重，当我们left或者是right移动一位所指向的值不变，那么就继续移动，此时我们需要注意指针是否会越界。然后对固定的数进行去重操作，i向右移动时，如果指向的数不变，则继续向右移动。
完整代码实现：
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret = new ArrayList<>(); //第1步，排序 Arrays.sort(nums); //第2步，双指针算法解决 int len = nums.length; for (int i = 0; i < len;) { if(nums[i] > 0) break; int left = i+1, right = len-1, target = -nums[i]; //利用查找两数之和的算法思想 while(left < right){ int sum = nums[left] + nums[right]; if(sum < target) { left++; } else if (sum > target) { right--; } else if (sum == target) { ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right]))); left++;right--;//缩小区间，继续寻找 //去重操作，同时要防止指针越界 while(left<right && nums[left]==nums[left-1]) left++; while(left<right && nums[right]==nums[right+1]) right--; } } i++; while(i<len && nums[i] == nums[i-1]) i++; } return ret; } }1.4. 四数之和
这道题与三数之和的解法类似，同样对数组进行排序，先固定一个数a，再去寻找三数之和target - a，接着固定一个数b，再去寻找两数之和target - a - b。寻找出的四元子数组依然是要不重不漏。
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ret = new ArrayList<>(); //第一步，排序 Arrays.sort(nums); //利用双指针解决 int len = nums.length; for (int i = 0; i < len; ) {//固定第一个数 for (int j = i+1; j < len; ) {//固定第二个数 int left = j+1,right = len-1; long aim = (long)target-nums[i]-nums[j]; while(left < right){ int sum = nums[left] + nums[right]; if(sum < aim) left++; else if (sum > aim) right--; else { ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--])); while(left<right && nums[left]==nums[left-1]) left++; while(left<right && nums[right]==nums[right+1]) right--; } } j++; while(j<len && nums[j]==nums[j-1]) j++; } i++; while(i<len && nums[i]==nums[i-1]) i++; } return ret; } }