优选算法的灵动之章：双指针专题(二)
专栏：算法
个人主页：手握风云
目录
一、算法例题
1.1. 复写零
1.2. 快乐数
1.3. 三数之和
1.4. 四数之和
一、算法例题
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;
}
}