【算法】【优选算法】双指针（上）

一、双指针简介

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是快慢指针。

1.1 对撞指针（左右指针）

对撞指针：⼀般⽤于顺序结构中，也称左右指针。

对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼
近。
对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是：
left == right （两个指针指向同⼀个位置；
left > right （两个指针错开；

1.2 快慢指针

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。
快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。

二、283.移动零

题目链接：283.移动零
题目描述：

题目解析：
这道题目要求十分清晰，把0全部放到非0元素后，且非0元素顺序不变。

解题思路：
我们使用两个指针：

指针dest指向，已经被处理过全是非0的数的最后一个坐标；
指针cur指向，非0元素。
使用这两个指针我们将数组分成了3片区域[0, dest]全是非0，[dest+1,cur-1]全是0，[cur,nums.length-1]未处理区。
所以我们只需要将cur位置的元素与dest+1位置元素交换即可。
由与存在第一个数就是nums[0] = 0的可能，所以dest初始值为-1。
然后再后续cur遍历数组过程中cur遇到非0就交换，dest到dest+1位置。

解题代码：

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public void moveZeroes(int[] nums) {
        
        int dest = -1;
        for(int cur = 0;cur < nums.length; cur++) {
            if(nums[cur] != 0) {
                int temp = nums[++dest];
                nums[dest] = nums[cur];
                nums[cur] = temp;
            }
        }
    }
}

三、1089.复写零

题目链接：1089.复写零
题目描述：

题目解析：数组长度固定，当从前往后遇到0就在该0和后面元素中插入一个0。

3.1 双指针解题

思路来源：

异地（即拿两个数组）操作时：我们遇到非0就填入另一个数组，遇到0时就填两个0。
那么我们就地（该数组上操作）操作时，我们直接模拟上面的操作，
先考虑两指针从前往后时，当遇到0就将下一个位置也置为0，但是这样我们就拿不到下一个位置的值，也不要说记录下来就行，你也不知道几个0连在一起，需要记录几次。
再考虑从后往前看。

解题思路：

指针dest指向，最后结果的最后一个数，例如示例一就指向下标为6的nums[6] = 4。
指针cur指向，数组尾即arr.length-1。
我们将dest向前走，遇到0时cur下标和cur前一个元素都置为0，即arr[cur–] = 0执行两次
遇到非0就直接将cur下标元素置为arr[dest]即可。
特殊情况，如果我们最后需要写的是0，只就需要单独执行一次arr[cur–] = 0，就像下面这种情况，如果不单独处理，我们的cur就需要减4次，就会造成数组越界。
在查找dest初始位置的时候，我们只需要让dest先遍历一遍数组，记录遇到0的个数，当0个数与dest下标和等于数组长度-1的时候，此时的dest就是初始位置。

解题代码：

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public void duplicateZeros(int[] arr) {
        int zeroNum = 0;//需要复写0个数
        int dest = 0;
        for(; dest < arr.length; dest++) {
            if(arr[dest] == 0) zeroNum++;
            if(dest + zeroNum >= arr.length - 1) break;
        }
        int cur = arr.length - 1;
        //特殊情况
        if(dest + zeroNum > arr.length - 1) {
            arr[cur--] = arr[dest--];
        }
        
        while(dest >= 0) {
            if(arr[dest] != 0) {
                arr[cur--] = arr[dest--];
            }else {
                arr[cur--] = 0;
                arr[cur--] = 0;
                dest--;
            }

        }
    }
}

3.2 暴力解法

解题思路：

我们从前向后遍历数组，当遇到arr[i+1] == 0的时候就将后续元素整体向后移动腾出 i+1 下标存放0。
整体向后移动思路，用一个变量将前一个数组元素记录下来，与当前元素交换，且该变量更新为当前元素值。

解题代码：

//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public void duplicateZeros(int[] arr) {
        int len = arr.length;
        for(int i = 0; i < len - 1; i++) {
            if(arr[i] == 0) {
                int prev = arr[i+1];                 
                for(int j = i + 2; j < len; j++) {
                    int tmp = arr[j];
                    arr[j] = temp;
                    prev = tmp;
                }
                arr[++i] = 0;
            }
        }
    }
}

四、202.快乐数

题目链接：202.快乐数
题目描述：

4.1 快慢指针

题目解析：

快乐数的定义题目已经给的非常详细了，但是我们最值得注意的是无限循环，这句话的意思就是无论是不是快乐数，都会循环。
其实这个无限循环的原理是因为 int最大值2^31 - 1 = 2147483647，就算是9999999999这样10个9的各位数平方和为810，所以在这个int范围中的各位数平方和一定会落到 [0,810]之间，所以最多循环811次就会出现重复的数了。
这就可以使用快慢指针，当指针值相同的时候，我们只需要判断这个值是否为1即可。

解题代码：

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public boolean isHappy(int n) {
        int slow = sum(n);
        int fast = sum(sum(n));
        while(slow != fast) {
            slow = sum(slow);
            fast = sum(sum(fast));
        }       
        return slow == 1;
    }
    //求各位数平方和
    private int sum(int n) {
        int sum = 0;
        while(n > 0) {
            sum +=(n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
}

4.2 暴力解法

解题思路：
我们只需要使用一个栈来将每次的平方和记录下来，判断是否其中已经有该值，此时值为1就是快乐数，不为1就不是快乐数。

题目代码：

//时间复杂度O(n)
//空间复杂度O(n)
import java.util.*;
class Solution {
    public boolean isHappy(int n) {
        int[] arr = new int[820];
        int i = 0;
        arr[i++] = n;
        while(true) {
            int temp = 0;
            while(n > 0) {
                temp += (n % 10) * (n % 10);
                n /= 10;
            }
            n = temp;
            if(contains(arr,n,i)) break;
            else arr[i++] = n;
        }
        return n == 1;
    }
    //判断是否包含
    private boolean contains(int[] arr, int n, int len) {
        for(int i = 0; i < len; i++) {
            if(arr[i] == n) return true;
        }
        return false;
    }
}

五、11.盛最多⽔的容器

解题代码：11.盛最多⽔的容器
题目描述：

题目分析：

这道题就是算容积（即两边下标差值和两边最短的乘积）最大。

5.1 左右指针

解题思路：

我们可以分析，当我们最开始时区底边最大也就是左指针为0，右指针为height.length-1。
如果我们移动指针，底边大小一定减小。
而高是有两边最小值决定，当我们移动较大值的指针时，后续的高一定是小于等于此时的高，这样高也减小，容积就是一直减小的。
而我们移动较小值的指针时，后续的高是有可能超过此时的高的，容积就有机会变大。
所以我们每次移动较小值的指针。
容积计算(right - left) * Math.min(height[left], height[right])。

解题代码：

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int maxArea(int[] height) {
        int ret = 0;
        int left = 0;
        int right = height.length - 1;
        while(left < right) {
            ret = Math.max(ret, (right - left) * Math.min(height[left], height[right]));
            if(height[left] < height[right]) left++;
            else right--;
        }
        return ret;
    }
}

5.2 暴力解法

解题思路：
反正是求容积的最大值，我们直接使用两层for循环将每个容积可能列举出来求最大值即可。
但是会超时。

解题代码：

//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int maxArea(int[] height) {
        int ret = 0;
        for(int i = 0; i < height.length - 1; i++) {
            for(int j = i + 1; j < height.length; j++) {
                 ret = Math.max(ret, (j - i) * Math.min(height[j], height[i]));
            }
        }
        return ret;
    }
}