知识文档站

Appearance

双指针

基本介绍 ​

解题思路 ​

设置两个指针的技巧，其实这种说法很宽泛，似乎没什么可总结的 ​

有时候所谓的双指针技巧，就单纯是代码过程用双指针的形式表达出来而已，没有单调性（贪心）方面的考虑 ​

有时候的双指针技巧包含单调性（贪心）方面的考虑，牵扯到可能性的取舍，对分析能力的要求会变高，其实是先有的思考和优化，然后代码变成了双指针的形式 ​

所以，双指针这个 “ 皮 ” 不重要，分析题目单调性（贪心）方面的特征，这个能力才重要。 ​

双指针类型 ​

同向双指针 ​

快慢双指针 ​

从两头往中间的双指针 ​

其他 ​

按奇偶排序数组 ​

题目链接 ​

https://leetcode.cn/problems/sort-array-by-parity-ii/ ​

题意：奇数放在奇数位上，偶数放在偶数位上 ​

思路分析 ​

设定两个指针，一个初始在 0 位置，遍历偶数位置，一个初始在 1 位置，遍历奇数位置，两个指针每次移动 2 个位置 ​

始终盯着最后一个元素看，看看发货到哪个指针对应的位置上 ​

一旦有一个指针越界，此时数组就排好了，因为一个指针遍历完数组，则说明该指针对应的位置排好了，由于不是奇数就是偶数，另一个位置肯定也是排好的 ​

代码实现 ​

java
class Solution {
    // 时间复杂度 O（1），额外空间复杂度 O（1）
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        // odd 奇数指针，even 偶数指针
        // 只要又一个指针越界，则数组排序完毕
        for (int odd = 1, even = 0; odd < n && even < n;) {
            // 始终盯着最后一个数，看发货到哪
            if ((nums[n - 1] & 1) == 1) {
                swap(nums, odd, n - 1);
                odd += 2;
            } else {
                swap(nums, even, n - 1);
                even += 2;
            }
        }
        return nums;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

寻找重复数 ​

题目链接 ​

https://leetcode.cn/problems/find-the-duplicate-number/ ​

思路分析 ​

构建一个链表，每个节点的信息表示下标索引，起始为 0 位置，每次根据该位置的上的值知道连接的下一个节点和信息 ​

例如数组 [ 2, 3, 1, 5, 4, 2 ]，初始为 0 位置，0 位置上的值是 2，下一个链接节点为 2 位置，2 位置上的值是 1，下一个链接的节点是 1 位置......得到链表：0 -> 2 -> 1 -> 5 -> 4 -> 2 ​

最后又回到了 2 位置，说明该位置上的值是重复的，即本题转化为环形链表找入环节点的值 ​

定义快慢指针，初始时先让快指针走 1 步，慢指针走 2 步，之后循环开始，慢指针每次走 1 步，快指针每次走 2 步，快指针和慢指针一定会在环上相遇，此时让快指针回到起点，两个指针每次走 1 步，相遇即为入环节点处 ​

代码实现 ​

java
class Solution {
    public int findDuplicate(int[] nums) {
        // 节点小于 2 不可能形成环，即无重复的数字
        if (nums == null || nums.length < 2) {
            return -1;
        }
        // 先让快指针朓 1 步，慢指针朓 2 步
        int slow = nums[0];
        int fast = nums[nums[0]];
        // 慢指针每次朓 1 步，快指针每次朓 2 步
        // 过程中一定会在环上相遇
        while (slow != fast) {
            // 指针每次根据该位置的上的值知道下一次跳到哪
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        // 快指针回到起点，两个指针每次走 1 步，相遇即为入环节点处
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

接雨水 ​

题目链接 ​

https://leetcode.cn/problems/trapping-rain-water/ ​

思路分析 ​

可以单点分析每个柱子能接住多少雨水，最后将数值累加起来就是答案 ​

每个柱子能接住的雨水数量取决于左右区间最高的柱子中较小的那一个，即问题转换为在当前柱子的左右区间内分别找到柱子的最大值，取最大值较小的柱子的高度记为最小值，这个最小值和当前柱子高度的差值就是当前柱子能接到雨水的数量 ​

考虑特殊情况，如果当前柱子比左右区间范围内的最大高度的柱子都高，即差值为负数，说明当前柱子无法接到雨水，差值还得和 0 取最大值才是答案 ​

求每个位置左右区间范围内的最大值可以借助辅助空间实现 ​

代码实现 ​

java
class Solution {
    // 原来这里是 int[] height，这里改成 nums
    public int trap(int[] nums) {
        int n = nums.length;
        int[] lmax = new int[n];
        int[] rmax = new int[n];

        lmax[0] = nums[0];
        // 0 - i 范围上的最大值，记录在 lmax[i] 中
        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i - 1], nums[i]);
        }

        rmax[n - 1] = nums[n - 1];
        // i - n-1 范围上的最大值，记录在 rmax[i] 中
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], nums[i]);
        }

        int ans = 0;
        // 认为数组越界部分为无穷小，首尾元素无法接住雨水，跳过
        for (int i = 1; i < n - 1; i++) {
            ans += Math.max(Math.min(lmax[i - 1], rmax[i + 1]) - nums[i], 0);
        }
        return ans;
    }
}

双指针优化 ​

认为首尾越界部分的高度为无穷小，所以首尾元素的位置不可能接到雨水，因此在 1 位置和 n - 2 位置定义指针，l 到 r 表示有可能接到雨水的位置，同时设置两个变量 lmax，rmax ​

lmax：不包括 l 位置，l 位置左侧的最大值 ​

rmax：不包括 r 位置，r 位置右侧的最大值 ​

lmax 和 rmax 中谁小，则 l 或者 r 位置的能接到雨水的数量就可以结算了，因为能否接到雨水取决于高度较小的柱子，结算后，移动指针，更新最大值 ​

java
class Solution {
    // 原来这里是 int[] height，这里改成 nums
    public int trap(int[] nums) {
        int l = 1;
        int r = nums.length - 1;
        int lmax = nums[0];
        int rmax = nums[nums.length - 1];
        int ans = 0;
        while (l <= r) {
            // 哪一侧的最大值小，就结算哪一侧
            if (lmax <= rmax) {
                ans += Math.max(lmax - nums[l], 0);
                lmax = Math.max(lmax, nums[l]);
                l++;
            } else {
                ans += Math.max(rmax - nums[r], 0);
                rmax = Math.max(rmax, nums[r]);
                r--;
            }
        }
        return ans;
    }
}

救生艇 ​

题目链接 ​

https://leetcode.cn/problems/boats-to-save-people/ ​

思路分析 ​

首先对数组排序，在首尾定义双指针，类似贪心思想，一个较大体重的和一个较小体重的组合，如果体重之和小于 limit，那二者就一艘船，如果大于 Limit，则大体重的自己一艘船，移动指针，较小的再去匹配体重次大的，看是否有机会一艘船 ​

代码实现 ​

java
class Solution {
    // 时间复杂度 O（n * logn），空间复杂度 O（1）
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int ans = 0;
        int l = 0;
        int r = people.length - 1;
        int sum = 0;
        while (l <= r) {
            // 如果 l，r 指向相同位置，取 1 个，不要多算了
            sum = l == r ? people[l] : people[l] + people[r];
            if (sum > limit) {
                r--;
            } else {
                l++;
                r--;
            }
            ans++;
        }
        return ans;
    }
}

题目扩展 ​

在前面要求的基础上，加上一个要求：体重之和必须是偶数 ​

问题分析：分析奇偶性，偶数 + 偶数 = 偶数，奇数 + 奇数 = 偶数，偶数加奇数不可能为偶数，将原数组分成奇数数组和偶数数组，分别求答案，最后结果累加即可 ​

盛水最多的容器 ​

题目链接 ​

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

思路分析 ​

首先明确一点，答案的结算肯定是以高度较小的柱子为标准 ​

在首尾设置指针，谁小就以谁为标准计算答案，结算完答案后移动指针 ​

类似贪心思想，面积尽可能大，宽和高也要尽可能的大，不断更新答案 ​

代码实现 ​

java
class Solution {
    // 时间复杂度 O（n），空间复杂度 O（1）
    public int maxArea(int[] height) {
        int ans = 0;
        for (int l = 0, r = height.length - 1; l < r;) {
            // 哪个柱子矮，以谁为标注结算答案
            ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
            // 结算答案后移动指针
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

供暖器 ​

题目链接 ​

https://leetcode.cn/problems/heaters/ ​

思路分析 ​

首先对两个数组排序，使用双指针，从两个数组的起点开始，对于每一个房屋，计算与每个供暖器位置的差值，即半径，为每一个房屋位置匹配位置最优的供暖器，得到最优半径 ​

heaters [ j ] - houses [ i ] 的绝对值表示半径，当 j 指针移动下一个位置时，比较两个差值谁更小，取较小的，遍历一遍数组后所有房屋都匹配到了最优的半径，在其中求最大值即可 ​

⚠️ 注意：当前后两个差值相同时，一定要让 j 移动到下一个位置，因为后续可能会有更优的解 ​

代码实现 ​

java
class Solution {
    // 时间复杂度 O（n * logn），额外空间复杂度 O（1）
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0;
        for (int i = 0, j = 0; i < houses.length; i++) {
            // i 号房屋，j 号供暖器匹配，半径不是最优的，让 j 动
            while (!best(houses, heaters, i, j)) {
                j++;
            }
            // 如果是最优的，不断更新最优半径中的最大值
            ans = Math.max(ans, Math.abs(houses[i] - heaters[j]));
            // 每个房屋匹配到最优半径后，i++ 来到下一个房屋
        }
        return ans;
    }

    // 这个函数含义：
    // 当前的地点houses[i]由heaters[j]来供暖是最优的吗？
    // 当前的地点houses[i]由heaters[j]来供暖，产生的半径是a
    // 当前的地点houses[i]由heaters[j + 1]来供暖，产生的半径是b
    // 如果a < b, 说明是最优，供暖不应该跳下一个位置
    // 如果a >= b, 说明不是最优，应该跳下一个位置
    public boolean best(int[] houses, int[] heaters, int i, int j) {
        // j 来到末尾位置，说明之前的供暖器的位置不是最优的，才会导致 j 的移动
        return j == heaters.length - 1 ||
                Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);
    }
}

缺失的第一个正数 ​

题目链接 ​

https://leetcode.cn/problems/first-missing-positive/ ​

思路分析 ​

由于 0 不是正整数，本题的期望是 i 位置的元素值为 i + 1，每个数字收集全且无重复数字 ​

定义 l 指针：不包括 l 指针位置，l 左边的的元素都符合 i 位置上元素的值为 i + 1，初始 l 在 0 位置，永远盯着 l 位置的数字，看能不能扩充 ​

定义 r 指针：包括 r 位置，r 右边的元素表示垃圾区，同时表示期望，假设数组长度为 n，则初始的期望是 l 位置左边的区域可以收集 1 - n 范围内的这些正整数。如果垃圾区扩大，则期望减少，初始 r 在 n 位置 ​

遵循以下五条规则，当 l 和 r 相撞，整个过程结束，最后返回 l + 1 就是缺失的最小正整数 ​

（1）arr[ l ] = l + 1，l++，符合期望 ​

（2）arr[ l ] ≤ l，比 i 位置的期望还小，放到垃圾区 ​

（3）arr[ l ] > r，整体期望为 1 - n，r 初始在 n 位置，比整体期望还大，放到垃圾区 ​

（4）arr[ a [ l ]- 1 ] == a [ l ]，本是符合要求的，但期望位置的值和当前元素重复，放到垃圾区 ​

（5）l 位置的数不是垃圾，也不是重复数字，交换到该放到的位置 ​

代码实现 ​

java
class Solution {
    // 时间复杂度 O（n），额外空间复杂度 O（1）
    public int firstMissingPositive(int[] nums) {
        // l 位置不包括 l，其左边区域中 i 位置的值都是 i + 1
        // 永远盯着 l 位置的数字，看能不能扩充
        int l = 0;
        // r 位置包括 r，其右边的区域是垃圾区
        // r 也表示期望，数组长度为 n，初始 r = n
        // 整体期望为能够收集 1 - n 这些数字，且无重复数字
        // 如果垃圾区扩充，整体期望变差
        int r = nums.length;
        // 当 l 和 r 相撞时，整个过程结束，l + 1 即为答案
        while (l < r) {
            if (nums[l] == l + 1) {
                l++;
            } else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
                // 违背期望的都放到垃圾区
                r--;
                swap(nums, l, r);
            } else {
                // 期望为 l 位置上方 l + 1
                // nums[l] - 1 表示期望的位置
                swap(nums, l, nums[l] - 1);
            }
        }
        return l + 1;
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1