双指针算法优选题详解

独断万古他化

发布于 2026-01-15 13:13:41

770

文章被收录于专栏：Java 攻略Java 攻略

1. 移动零

题目：

1> 题目解析

根据题目可知相对顺序不变，并且不能开辟数组，只能对原数组进行操作。

2> 算法思路

移动零这道题可以归为一类题，这类题为数组划分或者叫数组分块。这类题的特点是给了一个数组，制定了一个规则，在这个规则下将数组划分为若干个区间。那么这道题就是划分为两个区间，一个区间全为0，一个区间全非零。这类题的解法都可以使用双指针算法解决。(此处双指针是利用数组下标充当指针)

双指针解法：定义两个指针dest，cur，两个指针将整个数组划分为三个区间。cur指针从左向右扫描数组，遍历数组，cur右边全为待处理区间，左边为处理过区间。dest在处理过区间又划分为两个区间，dest左侧为非零区间，右侧到cur为全零区间。因此划分为[ 0,dest ]，[ dest+1,cur-1 ]，[ cur,n-1 ]三个区间，当cur指针移动到 n 时，待处理区间就没有了，此时dest将整个数组划分为非零与全零两个区间，此时就完成了移动零。

因此刚开始使cur指向下标0，dest为非零元素的最后一个位置，将其指向下标-1。cur移动时，当遇到零时，cur不做任何处理并向右移动一位；当为非零元素时，使dest向右移动一位，交换dest和cur位置的元素。然后重复这个过程，直到cur移动到下标为数组长度。

3> 代码

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

                int temp = nums[i];
                nums[i] = nums[dest];
                nums[dest] = temp;
            }
        }
    }
}

2. 复写零

题目;

1> 题目解析将数组中的零重复一次，但是不能越界，且只能在当前数组进行修改，不能开辟新数组。

2> 算法思路

双指针解法：

先找到最后一个" 复写 “的数定义cur指向0下标(从前往后遍历数组，决定dest向后移动一步还是两步)，dest指向-1下标(用来指向最后一个复写的数)。步骤：先判断cur位置的值，根据值判断dest移动几步，然后判断dest是否已经到边界结束位置，没有到则cur向后移动一步，重复这个步骤。如果dest到了最后一步，那么cur指向的元素就是最后一个” 复写 "的数。但是还有一种情况，当cur指向的最后一个复写数为0时，dest会出现越界问题。因此需要做特殊处理，使dest向前移动两步。
从后向前完成复写操作

3> 代码

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;

        while(cur < arr.length){
            if(arr[cur] != 0){
                dest++;
            }else {
                dest += 2;
            }
            if(dest >= arr.length-1){
                break;
            }
            cur++;
        }

        if(dest == arr.length){
            arr[arr.length-1] = 0;
            dest -= 2;
            cur--;
        }

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

3. 快乐数

题目：

1> 题目解析根据定义可知取每一位的平方和最后只有两个结果，要么重复1，要么无限循环（为什么没有第三种情况一直平方下去不重复呢，此处可以用鸽巢定理进行证明）。那么可以将两种情况并为一类，最后都会循环形成一个环，只是一个环里全是1 ，一个环里数值都不一样。这类似于链表中是否有环的问题，可以用双指针解决。

2> 算法思路

双指针解法：此处双指针指的是数而不是真的指针，将每一个平方和的数作为一个指针，慢指针每一次进行一次平方和操作，快指针每一次进行两次平方和操作。最后都会进入环，只需要判断相遇时的数值是否等于1 即可，若为1 就是快乐数，不是1 则不是快乐数。

3> 代码

class Solution {
    public int bitsum(int n){
        int sum = 0;
        while (n != 0){
            int x = n%10;
            sum += x*x;
            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;
    }
}

4. 盛最多水的容器

题目：

1> 题目解析最大储水量为两个元素坐标之差与两元素的最小值的乘积

2> 算法思路

解法一：暴力解法：两个for循环全部枚举出来选出最大的。
解法二：双指针解法：发现求的体积 V = h * w ，当w减小时体积减小，h减小时体积减小，两个都减小时体积减小。那么随便取出一段例如[ 2, 5 ]，当下标2向右移动 w势必会减小，体积变小，那么就不需要再枚举两个之间的元素了，只需要求边界的体积就行。因此第一步直接取两侧的元素为双指针求其体积，然后让值小的元素向内移动，再求体积，依次重复将体积求出来，直到左右指针相遇，将最大的体积返回即可，这样就只需遍历数组一遍即可，时间复杂度为O(n)。

3> 代码

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

5. 有效三角形个数

题目：

1> 题目解析

从题中可知我们需要找到能够满足能够三角形的三个元组，并返回构成的个数。示例中说明如果出现重复元素，那么重复的元素不能跳过。

2> 算法思路前提：判断是否为三角形，需要判断任意两个数是否大于第三个数，也就是（a+b > c；a+c > b；b+c > a）全部满足才可以，但是这需要判断三次。还有更简便的判断，当已知有序时，只需要判断小的两个数是否大于最大数即可（a < b < c；判断 a+b < c），因为c 是最大的，不论和谁相加都一定大于剩下的，因此只需要判断一种情况。

解法一：暴力解法将所有情况全部枚举出来，并返回可能的结果数。这个解法需要使用3层for循环来解决，此解法时间复杂度为O(n3)，并且每次都需要判断三次，时间复杂度为O(3n3)，耗时太长。
解法二：双指针解法先将数组进行排序，此时复杂度为O(nlogn) 然后使用有序的单调性，固定最大的数，将其视为第三边，左右指针分别指向最大数左边的两个边界，然后判断。

此时有两种情况：

情况一：左右相加大于固定值，因为数组有序，左边最小的加上右边已经大于固定值了，那么左指针向右移动变大，相加一定大于固定值，因此这些不用再计算，直接让右指针减去左指针算出区间里所有的个数。然后右指针向左移动再次判断。
情况二：左右相加小于等于固定值，因为数组有序，右指针最大的数加上左指针的数都小于固定值了，那右指针向左移动变小，相加肯定小于固定值，因此不需要进行此操作。让左指针向右移动再次判断，直到左右指针相遇，然后让固定值左移一位重复上述操作。此时的时间复杂度为O(n2)。

动画演示:

3> 代码

class Solution {
    public int triangleNumber(int[] nums) {
        //先排序
        Arrays.sort(nums);

        int ret = 0,n = nums.length - 1;
        for(int i = n; i >= 2;i--){
            int left = 0,right = i - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }
}

6. 和为S的两个数

题目：

1> 题目解析从题中看出数组为有序数组，那么就可以利用单调性来解决。

2> 算法思路

解法一：暴力解法两层for循环将所有的情况枚举出来，返回正确的结果。耗时较长。
解法二：双指针解法开始时左右指针分别指向数组的边界，判断和与tartget的关系，此时有三种情况情况一：当和大于target时，因为数组有序递增，左指针指向的最小数和右指针指向数相加已经大于目标值了，若左指针向右移动变大，和会更大，因此使右指针向左移动，再次判断。情况二：当和小于target时，因为数组递增，右指针指向的最大值加上左指针指向数已经小于目标值了，若右指针向左移动变小，和会变小，因此使左指针向右移动，再次判断，直到左右指针相遇。情况三：当和刚好等于目标值时，此时直接返回即可。

3> 代码

class Solution {
    public int[] twoSum(int[] price, int target) {
        int left = 0,right = price.length - 1;
        while(left < right){
            int 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};
    }
}

7. 三数之和

题目：

1> 题目解析 i!=j，i!=k，j!=k说明了三元组下标不能重复，也就是同一个元素不能用两次，且三元组相加后的结果应该为0。答案中不能出现重复的三元组，从示例来看，也就是[ -1,0,1 ]和[ 0,1,-1 ]只能算一个。

2> 算法思路这道题和上面的和为S的两数相似，难的地方在于去重操作。可以先排序，这样取出来的重复三元组的里的顺序是一样的，方便去重。

解法一：暴力解法先排序，使用三层for循环遍历到每一个符合要求的三元组，然后使用set容器进行去重。此法时间复杂度为O(n3)
解法二：双指针解法先排序，然后固定一个数（这个数要小于等于0，如果大于0，右边边界再找两个数和它相加是永远大于0的），在该数的后边区间使用双指针算法快速找到两个和为固定值负数的数。此过程和上道题一样。

此题的细节问题：

去重问题：这里去重不使用容器，使用另一种解法。当找到一种结果之后，left和right指针都需要跳过重复元素，例如[ -4,-4,-1,-1,0,0,1,2,5,6 ]，当固定-4时，left指针为-1，right指针为5时，此时找到了一种结果，但是当left指针向右移动一位仍为-1，此时就重复了，因此算法实现时，要让指针指向重复时一直向左(右)移动，直到元素不重复并循环上述操作。当使用完一次双指针算法时，还需要将固定数下标也跳过重复元素，因为固定数也可能出现重复。但是这个去重操作会出现数组越界问题，示例[ 0,0,0,0, 0]，当这种情况时，左右指针为了去重会不断向左(右)进行移动，直到越出数组边界，因此需要添加判断条件。
不漏问题：当找到一种结果时不要" 停止 "，上一道题使用双指针找到一个解返回即可，但这道题需要返回所有的结果。因此当找到一个解时要继续缩小区间继续寻找，直到找到所有解。

3> 代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);

        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];
            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--;
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                }
            }

            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }

        return ret;
    }
}

8. 四数之和

题目

1> 题目解析这个题和上面的三数之和基本上一样，只是多了一个数。因此可以利用三数之和来解这道。

2> 算法思路利用三数之和的方法解

解法一：暴力解法先排序，四层for循环找到所有解，使用set容器去重。
解法二：排序 + 双指针 + 三数之和先将数组排序为有序递增数组。然后固定一个数a，在a后面的区间使用" 三数之和 " 找到三个数，使这三个数和等于 target - a 即可。如何利用三数之和：就是上道题的思路，先依次固定一个数 b ，在b后面的区间，利用" 双指针 "使这两个数的和等于 target - a - b 即可。

细节问题：和" 三数之和 "一样

去重：这里多了一层固定数，因此去重需要三处地方进行去重操作，分别是左右指针，第二个固定数，第一个固定数。
不漏：找到一种解法后继续进行，找所有满足的四元组。

3> 代码

class Solution {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();

        //1. 先排序
        Arrays.sort(nums);
        //2. 固定一个值
        int n = nums.length;
        for (int i = 0; i < n; ) {
            long tempi = (long)target - nums[i];
            for (int j = i + 1; j < n; ) {
                long tempj = tempi - nums[j];
                int left = j + 1,right = n - 1;
                while (left < right){
                    int sum = nums[left] + nums[right];
                    if(sum < tempj) left++;
                    else if(sum > tempj) right--;
                    else {
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],
                                nums[left],nums[right])));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left-1]) left++;
                        while (left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                j++;
                while (j < n && nums[j] == nums[j-1]) j++;
            }
            i++;
            while (i < n && nums[i] == nums[i-1]) i++;
        }

        return ret;
    }
}

结语：本文讲述了双指针算法题目的一些解法思路，如有问题望各位大佬给出指正。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-19，如有侵权请联系 cloudcommunity@tencent.com 删除

排序