优选算法的灵动之章：双指针专题(二)

专栏：算法

个人主页：手握风云

一、算法例题

1.1. 复写零

1.2. 快乐数

1.3. 三数之和

1.4. 四数之和

一、算法例题

1.1. 复写零

题目要求我们要进行就地修改，并且函数不返回任何类型。我们先思考两个数组异地修改。我们同样是定义两个指针cur和dest。当cur指向非零元素时，dest直接照抄，然后统一向右移动一位；当cur指向零元素时，dest照抄两遍。

我们接着对异地操作进行优化，然后再思考就地操作。如果cur指向零元素时，就会把下一个元素给覆盖掉，导致后面都会被复写成零，所以两个指针从前向后完成复写操作是错的。那我们就换一种思路，从后向前完成复写。

由于题目要求不能超过原有数组的长度，所以我们首先要找到复写之后数组的最后一个元素。我们让cur指向非零元素，dest向右移动一位；如果cur指向零元素，dest向右移动两位。但此时还有一种特殊情况，如果复写之后最后一个元素为零，那么dest就会越界，所以我们还要单独处理一下边界，只需把倒数第二个元素直接复写成零，然后cur向前移动一位，dest向前移动两位。

完整代码实现：

java">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。

java">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循环来判断三数之和是否为零，由于题目不要求输出的顺序和三元组的顺序，所以我们需要对三元组进行去重的操作，那么此时的时间复杂度就是 $O(n^{3})$ 。

接着我们对解法进行优化，对于有序数组，我们可以想到二分查找或者是双指针。我们先固定第一个元素，然后从剩余的区间里面查找两数之和是否为被固定数字的相反数。查找两数之和，我们这里就不再多说。

接下来是去重操作。我们先对三元子数组进行去重，当我们left或者是right移动一位所指向的值不变，那么就继续移动，此时我们需要注意指针是否会越界。然后对固定的数进行去重操作，i向右移动时，如果指向的数不变，则继续向右移动。

完整代码实现：

java">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。寻找出的四元子数组依然是要不重不漏。

java">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;}
}