双指针算法

趙卋傑

发布于 2026-01-12 15:55:30

950

一.基本介绍

常见的双指针有两种形式，分别为对撞指针和快慢指针
对撞指针：一般用于顺序结构中，也称左右指针

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

快慢指针:又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。这种方法对于处理环形链表或数组非常有用。其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。 快慢指针的实现方式有很多种，最常用的一种就是: 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

二.移动零

1.题目解析

移动零题目链接

https://leetcode.cn/problems/move-zeroes/description/

数组分两块是非常常见的一种题型，主要就是根据一种划分方式，将数组的内容分成左右两部分，即处理和未处理 这种类型的题，一般就是使用「双指针」来解决。 利用数组下标来充当指针

2.算法原理

算法思路：定义cur指针来扫描整个数组，dest指针表示已处理的区间，也就是非零数序列的最后一个位置在cur遍历期间，使得[0,dest]的元素全部都是非零元素，[dest+1,cur-1]的元素全是零

算法流程：

初始化cur = 0用来遍历数组，因为不知道非零元素的最后一个位置，因此dest初始化为-1，dest永远指向的是已处理的最后一个元素即非零的最后一个元素
cur向后遍历会遇到两种情况： ①cur为0时，cur++ ②cur不为0时，dest++，并且交换cur 位置和dest 位置的元素，之后让 cur++ ，扫描下⼀个元素。

3.编写代码

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        for(int cur = 0,dest = -1;cur < n;cur++) {
            if(nums[cur] != 0) {
                dest++;
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
            }
        }
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        //时间复杂度O(n),空间复杂度O(1)
        int dest = -1;
        int cur = 0;
        while(cur < nums.length) {
            if(nums[cur] != 0) {
                dest++;
                int tmp = nums[dest];
                nums[dest] = nums[cur];
                nums[cur] = tmp;
                cur++;
            }else{
                cur++;
            }
        }
    }
}

三.复写零

1.题目解析

复写零题目链接

https://leetcode.cn/problems/duplicate-zeros/description/

操作数组中的元素往往也用双指针算法 先通过 "异地" 操作优化成双指针下的 "就地" 操作

转为一个数组内就地操作：

从前往后无法实现我们试试从后往前我们知道最后一个复写的数是4，所以我们假设cur就指向4

我们发现这么做可以实现复写零，并且也不会出现覆盖的问题，所以我们只需要找到最后一个复写的数是啥即可，也就是"4"的位置

2.算法原理

先找到最后一个复写的数 ①先判断cur位置的值 ②决定dest向后移动一步或者两步 ③判断一下dest是否已经到结束位置 ④cur++

处理边界情况（dest可能会出现越界情况）如果dest == n 发生越界，我们只需将arr[n-1]位置变为0即可，cur++,dest -= 2正常复写即可

从前往后进行复写零操作 cur用来从后往前进行遍历，dest表示进行复写的位置（结束标志为数组中最后一个元素的位置）

3.编写代码

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0,dest = -1,n = arr.length;
        //1.找到最后一个复写的数
        while(cur < n) {
            if(arr[cur] != 0) dest++;
            else dest += 2;
            if(dest >= n-1) break;    //dest到结束位置
            cur++;
        }
        //2.处理边界情况（dest会发生越界）
        if(dest == n) {
            arr[n-1] = 0;
            cur--;
            dest -= 2;
        }
        //3.从后往前正常完成复写操作
        while(cur >= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
}

四.快乐数

1.题目解析

快乐数题目链接

https://leetcode.cn/problems/happy-number/description/

对于这两种情况，我们可以抽象为一种类型，因为他们最终都会进入到一个环中进行循环，我们利用快慢指针一前一后来判断，当slow和fast值相同时就是快乐数（出现循环往复的情况时，均可考虑使用快慢指针的思想）

2.算法原理

快慢指针有⼀个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是1，那么这个数⼀定是快乐数；如果相遇位置不是1 的话，那么就不是快乐数。

定义快慢指针
慢指针每次向后移动一步，快指针每次向后移动两步
判断相遇时候的值即可

疑问？给定的数一定会进入循环吗？ 答案是肯定的，鸽巢原理进行简单证明（原理：当有n个巢，n+1个鸽时，至少有一个巢的鸽数大于1）给定数n的范围为整形的最大值，即2^31 - 1= 2147483647，我们选取更大的值9999999999（10个9），以此数进行快乐书计算也就是10个9^2相加，即为810，最大的变化范围为810，此时的810就为巢数，当鸽大于811时，必然会出现循环最终走向一个圈里

3.编写代码

class Solution {
    public int bitSum(int n){ //此方法实现 返回n的每一位平方后相加的数字
        int sum = 0;
        while(n != 0) {
            int t = n % 10;
            sum += t*t;
            n = n/10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n,fast = bitSum(n);
        while(slow != fast) {
            slow = bitSum(slow);//
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;//判断相遇后的值是否为1
    }
}

五.盛水最多的容器

1.题目解析

盛水最多的容器题目链接

https://leetcode.cn/problems/container-with-most-water/description/

2.算法原理

暴力枚举：我们将所有的情况一一进行枚举，再将他们的体积取最大值即可

利用单调性使用对撞指针来解决

3.编写代码

解法一：暴力枚举

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int ret = 0;
        for(int i = 0;i < n;i++) {
            for(int j = 1;j < n;j++) {
                ret = Math.max(ret, Math.min(height[i], height[j]) * (j - i));
            }
        }
        return ret;
    }
}

解法二：利用单调性使用双指针来解决

class Solution {
    public int maxArea(int[] height) {
        int left = 0,right = height.length - 1,ret = 0;
        while(left < right) {
            int v = Math.min(height[left],height[right]) * (right-left);
            ret = Math.max(ret,v);
            if(height[left] < height[right]) {
                left++;
            }else{
                right--;
            }
        }
        return ret;
    }
}

六.有效三角形的个数

1.题目解析

有效三角形个数题目链接

https://leetcode.cn/problems/valid-triangle-number/description/

2.算法原理

先对整个数组进行排序
固定最大数
利用单调性在最大的数的左区间内，使用对撞指针，快速统计出符合要求的三元组的个数

a+b>c时，a是最小的，所以[a,b]内的所有数字均满足条件，此时right--使得b变小判断下一种情况 a+b<=c时，b是最大的，所以[a,b]内的所有数字均不满足，我们left++使得a变大再进行判断利用单调性使用对撞指针来解决

3.编写代码

class Solution {
    public int triangleNumber(int[] nums) {
        //1.对数组进行排序
        Arrays.sort(nums);
        //2.利用双指针解决问题
        int n = nums.length,ret = 0;
        for(int i = n-1;i >= 2;i--) {
            int left = 0,right = i-1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    //[2,2,3,4,5,7,8]
                    //left = 2,right = 7,n = 8;
                    //left + right > i,表明[left,right]上的所有元素均可满足条件
                    //舍弃大的数，进行下一次判断
                    ret += right - left;
                    right--;
                }else{
                    //left = 2,right = 5,n = 7
                    //left + right <= i,表明[left,right]上的所有元素均不满足条件
                    //舍弃小的数进行下一次判断
                    left++;
                }
            }
        }
        return ret;
    }
}

七.和为s的两个数

1.题目解析

和为s的两个数题目链接

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

2.算法原理

利用单调性使用对撞指针来解决

3.编写代码

class Solution {
    public int[] twoSum(int[] price, int target) {
        //利用有序数组的单调性，使用双指针算法解决问题
        int n = price.length,sum = 0;
        int left = 0,right = n-1;
        while(left < right) {
            sum = price[left] + price[right];
            if(sum > target) {
                right--;
            }else if(sum < target) {
                left++;
            }else{
                return new int[] {price[left], price[right]};
            }
        }
        //照顾编译器，有返回值
        return new int[]{0};
    }
}

八.三数之和

1.题目解析

三数之和题目链接

https://leetcode.cn/problems/3sum/description/

根据上题的两数之和，相同的思路，我们先对数组进行排序，利用单调性+双指针算法 我们要求的是和为0的三个数，排序后我们先固定最大的一个数a，在该数之前寻找和为-a的数即可此外题目要求三元组不能重复，所以我们还要进行去重操作

2.算法原理

去重操作：

小优化：

3.编写代码

暴力解法（利用Set去重）:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums==null || nums.length<3){
            return new ArrayList<>();
        }
        Set<List<Integer>> res=new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j=i+1;j<nums.length;j++){
                for(int k=j+1;k<nums.length;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        res.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }
}

起始固定第一个元素(单调性+双指针算法)：

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //1.对数组进行排序
        Arrays.sort(nums);
        //2.固定一个数a
        int n = nums.length;
        for(int i = 0;i < n;) {
            if(nums[i] > 0) break;
            int left = i + 1,right = n-1,target = -nums[i];
            //3.在该数后面的区间利用双指针算法找到和为-a的两个数
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > target){
                    right--;
                }else if(sum < target) {
                    left++;
                }else{
                    //将找到的arr[i],arr[left],arr[right]添加到list中
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;right--;
                    //对left，right进行去重操作  注意越界问题
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
            }

            //对i进行去重,注意越界问题
            i++;
            while(i < n && nums[i] == nums[i-1]) {
                i++;
            }
        }
        return ret;
    }
}

起始固定最后一个元素：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);
        int n = nums.length;
        //2.固定一个数为a
        for(int i = n - 1;i >= 2;) {
            if(nums[i] < 0) break;
            int left = 0,right = i-1,target = -nums[i];
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > target) {
                    right--;
                }else if(sum < target) {
                    left++;
                }else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;right--;
                    //对left right 进行去重操作
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
            }
            //对i进行去重
            i--;
            while(i >= 2 && nums[i] == nums[i+1]){
                i--;
            }
        }
        return ret;
    }
}

九.四数之和

1.题目解析

四数之和题目链接

https://leetcode.cn/problems/4sum/description/

2.算法原理

3.编写代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0;i < n;){//固定a
            for(int j = i+1;j < n;) {//固定b
                int left = j+1,right = n-1;
                long aim = (long)target - nums[i] - nums[j];//a,b均固定，找另外两个数
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum > aim){
                        right--;
                    }else if(sum < aim){
                        left++;
                    }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进行去重,注意越界问题
                j++;
                while(j < n && nums[j] == nums[j-1]) {
                    j++;
                }
            }
            //对i进行去重,注意越界问题
            i++;
            while(i < n && nums[i] == nums[i-1]) {
                i++;
            }
        }
        return ret;
    }
}