我要成为算法高手-双指针篇

什么是双指针?

双指针算法是一种常见的解决问题的技巧，通常使用两个变量在链表或者数组中进行迭代、遍历，从而达到解决问题的目的。光说理论太抽象，我们来几道题目吧~~

问题1：移动零

力扣链接：移动零
在这里插入图片描述
分析一下题目要求： 将给定数组中所有的0移动到数组的末尾，也就是将数组分成两个区域，前半部分是非零元素，后半部分都是零，并且保持非零元素的相对顺序，如示例1，非零元素的顺序：1，3，12，处理之后非零元素的顺序也要是1，3，12，在这里插入图片描述

解题思路：
既然是双指针算法，那我们就定义两个"指针"咯，这里的"指针"，我们是指数组下标
定义两个"指针"，dest，cur，
dest：已经处理好的区间内，非0元素的最后一个位置
cur：从左往右遍历数组
dest初始为-1，表示刚开始还没非0元素，cur初始为0
在扫描的过程中，一直让数组保持下面这个状态就好了
在这里插入图片描述
图解：

代码实现：

public void moveZeroes(int[] nums) {
    //双指针:定义dest和cur,dest初始值为-1
    //dest的作用:非0元素的最后一个位置,也就是[0,dest]的区间是非0元素
    //cur的作用:从左往右扫描数组,遍历数组
    int dest = -1;
    for (int cur = 0; cur < nums.length; cur++) {
        if (nums[cur] != 0) {
            //cur遇到非0元素,先交换dest+1位置和cur位置的元素,再dest++,cur++
            int tmp = nums[dest + 1];
            nums[dest + 1] = nums[cur];
            nums[cur] = tmp;         
            dest++;
        }
    }
}

问题2：复写零

力扣链接：复写零
在这里插入图片描述
分析一下题目要求： 所谓复写，也就是让我们抄一遍数组的内容，遇到非零的直接抄这个数，遇到零抄两遍零，题目要求我们在原数组上进行操作，也就是说不能重新开辟一个新的数组

解题思路：
先找到最后一个需要被复写的数，然后从后往前进行复写，如果从前往后，后面的数会被覆盖掉。
如何找到最后一个被复写的数？还是利用双指针算法，如图
在这里插入图片描述
根据cur位置的值，判断dest向前走一步还是两步，走完判断dest是否到达结束位置（dest是否>=arr.length-1），如果dest没有到达结束位置，则让cur++。重复上面的步骤，当dest到达最后位置时，cur指向的就是最后一个被复写的数，要注意的是，dest的位置可能是arr.length-1，也可能是arr.length，如果dest=arr.length（如下图），需要处理这个边界问题，
在这里插入图片描述
处理办法：arr[arr.length - 1] = 0;dest -= 2;cur- -;

接下来就可以从后往前开始复写了，拿下图举例

代码实现：

    public void duplicateZeros(int[] arr) {
        int cur = 0;//指向最后一个位置
        int dest = -1;//dest指结果中,最后需要复写的位置,开始时不知道dest在哪,所以-1
        //先找到最后一个被复写的数
        while (cur < arr.length) {
            if (arr[cur] == 0) {
                dest += 2;
            } else {
                dest++;
            }
            if (dest >= arr.length - 1) {
                break;
            }
            cur++;
        }
        //边界情况,可能出现:最后要复写两个0,第二个0在arr.length这个位置
        if (dest == arr.length) {
            arr[arr.length - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0) {

            if (arr[cur] != 0) {
                arr[dest] = arr[cur];
                dest--;
            } else {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            cur--;
        }
    }

问题3：快乐数

力扣链接：快乐数
在这里插入图片描述
题目要求：题目让我们判断给定的数是不是快乐数，快乐数：每次都对这个数进行一次操作（让它的值替换为它每一位的数的平方之和），重复这个操作，判断最终结果是不是变成1或者无限循环变不到1
解题思路：有点类似之前写过的判断链表是否成环，题目说明了结果是1或者无限循环，但是其实1也是无限循环，1重复上述操作结果永远都是1，所以我们可以使用快慢指针的思想，当两个指针相遇时，判断两个指针指向的数是不是1即可（如果不熟悉判断链表是否成环，可以看这篇哦链表OJ）
在这里插入图片描述
代码实现：

//返回n的每一位的平方之和
public int func(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 fast = func(n);
    int slow = n;
    while (fast != slow) {
        slow = func(slow);
        fast = func(func(fast));
    }
    return fast == 1;
}

问题4：盛最多水的容器

力扣链接：盛最多水的容器
在这里插入图片描述
题目要求： 给定了n条垂线，题目要找出两条线，与X轴构成的容器最多能盛水的容积
解题思路： 容积V = h*w，其中，h指高度，也就是两条线的最短的那条，w指宽度

如图：

代码实现

public int maxArea(int[] height) {
    //根据规律:向内枚举时,要么宽度肯定减小,但是高度只能是不变或减小(木桶效应)
    int left = 0;
    int right = height.length - 1;
    int maxV = 0;
    int V = 0;
    while (left < right) {
        V = (right - left) * Math.min(height[left], height[right]);
        if (V > maxV) {
            maxV = V;
        }
        //让高度小的移动,高度小也叫说明容积小,不符合要求
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxV;
}

问题5：有效三角形个数

力扣链接：有效三角形个数
在这里插入图片描述
题目要求：
给定非负整数数组，在数组中挑3个能组成三角形数，求有几种挑法
解题思路：

代码实现：

    public int triangleNumber(int[] nums) {
        // 利用单调性,使用双指针算法
        int count = 0;
        int[] ret = nums;
        Arrays.sort(ret);// 先排个序
        int flg = ret.length - 1;//固定好flg,表示最大的数
        while (flg >= 2) {
            //固定好flg之后,再利用双指针
            int left = 0;
            int right = flg - 1;
            while (left < right) {
                if (ret[left] + ret[right] > ret[flg]) {
                    count += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
            flg--;
        }
        return count;
    }

问题6：查找总价格和为目标值的两个商品(两数之和)

力扣链接：查找总价格和为目标值的两个商品
在这里插入图片描述
题目要求： 给定数组和target（题目说明了已经排好序了），求数组中和为target的两个数，以数组的形式返回这两个数即可
解题思路： 定义双指针left，right分别指向第一个和最后一个元素，求两个指针指向的元素之和如果小于target，说明，要大一点！让left++，同理如果大于target，说明要小一点~~，让right–，当两个值等于target，此时可以返回了
代码实现：

    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];//返回的数组
        //定义双指针left,right
        int left = 0;
        int right = price.length - 1;
        while (left < right) {
            int sum = price[left] + price[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return ret;
    }

问题7：三数之和

力扣链接：三数之和
在这里插入图片描述
题目要求：
给定整数数组，判断是否存在相加和为0的三个数，这三个数的下标不能重复，也就是说这三个数下标是不一样的，返回所有的三元组，答案不能是重复的三元组
解题思路：

找到之后left和right继续移动，解决了不漏的问题，能够把所有的三元组都找出来，但是并没有满足题目要求：不能重复，解决办法就是：当找到两个数后，记录left和right的值，left和right跳过重复的数，另外，固定的数a（下标是flg）也要跳过重复的数
代码实现：

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//先排序
        int flg = 0;//固定一个的数
        List<List<Integer>> ret = new ArrayList<>();// 返回的List
        while (flg <= nums.length-2) {
            //双指针算法,left,right
            int left = flg + 1;//左指针
            int right = nums.length - 1;//右指针
            int a = nums[flg];//双指针找目标值和为-a的两个数
            if(a>0) {
                //小优化,大于0了,后面的都是>0的数,肯定找不到-a
                break;
            }
            //双指针算法,思路和求两数之和一样
            while (left < right) {
                if (nums[left] + nums[right] < (-a)) {
                    left++;
                } else if (nums[left] + nums[right] > (-a)) {
                    right--;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ret.add(list);//
                    // 找到结果之后,left,right跳过重复元素,避免越界
                    int leftNumber = nums[left];
                    int rightNumber = nums[right];
                    while (nums[left] == leftNumber && left < nums.length - 1) {
                        left++;
                    }
                    while (nums[right] == rightNumber && right > 0) {
                        right--;
                    }
                }
            }
            // flg也要跳过重复的元素,flg不能越界
            while (nums[flg] == a&&(flg <= nums.length-2)) {
                flg++;
            }
        }
        return ret;
    }

问题8：四数之和

力扣链接：四数之和
在这里插入图片描述
题目要求：
在给定数组中，找出4个和为target的数，这四个数的下标不能重复
解题思路：
明白了两数之和跟三数之和后，四数之和的思路就很简单了，先排序，固定一个数a（最左边或者最右边的数，都是一样的），然后在后面的区间按照三数之和的思路：固定一个数b，按照两数之和找出和为target-a-b的两个数
在这里插入图片描述
同样的，left、right、flg1、flg2也要跳过重复的数
代码实现：

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();// 返回的List
        for (int i = 0; i < nums.length; ) {//固定数a
            for (int j = i + 1; j < nums.length; ) {//固定数b
                int left = j + 1;
                int right = nums.length - 1;
                long aim = (long) target - (nums[i] + nums[j]);//a+b
                while (left < right) {
                    if (nums[left] + nums[right] < aim) {
                        left++;
                    } else if (nums[left] + nums[right] > aim) {
                        right--;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[right]);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        ret.add(list);
                        //处理细节,去重
                        int leftNumber = nums[left];
                        int rightNumber = nums[right];
                        while (nums[left] == leftNumber && left < nums.length - 1) {
                            left++;
                        }
                        while (nums[right] == rightNumber && right > 0) {
                            right--;
                        }
                    }
                }
                j++;
                while ((j < nums.length - 2) && nums[j - 1] == nums[j]) {
                    j++;
                }
            }
            i++;
            while ((i < nums.length - 3) && nums[i - 1] == nums[i]) {
                i++;
            }
        }
        return ret;