文章

双指针

双指针技术通过两个指针在同一序列上移动，常用于查找特定条件下的子数组、字符串匹配、排序等问题，提升效率。

发表于 更新于
作者 Sylvan
14 分钟阅读
双指针

双指针

  • 同向指针
  • 快慢指针
  • 从两端向中间的指针
  • 其他

922. 按奇偶排序数组 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(1)
    vector<int> sortArrayByParityII(vector<int> &nums) {
        int even = 0;
        int odd = 1;
        while (even < nums.size() - 1 && odd < nums.size()) {
            // 找到偶数下标，但元素是奇数的位置
            while (even < nums.size() - 1 && ((nums[even] & 1) == 0)) even += 2;
            // 找到奇数下标，但元素是偶数的位置
            while (odd < nums.size() && ((nums[odd] & 1) != 0)) odd += 2;
            // 交换
            if (even < nums.size() - 1 && odd < nums.size()) swap(nums[even], nums[odd]);
        }
        return nums;
    }
};

287. 寻找重复数

  • 要求 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(1)
    // 类似环形链表找入口节点，nums 数组类似静态链表
    int findDuplicate(vector<int> &nums) {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while (slow != fast) {
            // slow = slow.next
            slow = nums[slow];
            // fast = fast.next.next
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

42. 接雨水

  • 按行积累
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <vector>

using namespace std;

class Solution {
public:
    // 按行累积，每次累加当前行上能接多少水（超时）
    int trap(vector<int> &height) {
        int n = height.size();
        // 找最大高度
        int maxHeight = 0;
        for (const auto &item: height)
            maxHeight = max(maxHeight, item);

        int res = 0;
        // 每次找一层，一格一格的加
        for (int level = 1; level <= maxHeight; ++level) {
            int i = 0;
            // 找到第一个不低于当前 lever 的作为左边界
            while (i < n && height[i] < level) i++;
            // 找不到左边界，这层以及上面的层都接不了水
            if (i >= n) break;

            for (int water = 0; i < n; i++) {
                if (height[i] < level) {
                    // 已有左边界，并且比当前层低，说明这个格子 (i, lever) 可以放水
                    water++;
                } else if (height[i] >= level) {
                    // 找到大于或等于当前层的右边界，就把之前累积的水加到结果中，并清空 water
                    // 当前的右边界变成下一个左边界，在继续寻找下一个右边界
                    res += water;
                    water = 0;
                }
            }
        }
        return res;
    }
};
  • 按列积累
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(n)
    // 按列累积，每次累加当前列上能接多少水
    int trap(vector<int> &height) {
        int n = height.size();
        int res = 0;

        // 记录当前元素左边的最大值
        int leftMax = height[0];
        // 可以在后续累积雨水时遍历数组的操作中，用 leftMax 优化掉 leftMaxArr
        vector<int> leftMaxArr(n);
        // 更新每个元素左边的最大值
        for (int i = 1; i <= n - 2; ++i) {
            leftMaxArr[i] = leftMax;
            leftMax = max(leftMax, height[i]);
        }

        // 记录当前元素右边的最大值
        int rightMax = height[n - 1];
        vector<int> rightMaxArr(n);
        for (int i = n - 2; i >= 1; i--) {
            rightMaxArr[i] = rightMax;
            rightMax = max(rightMax, height[i]);
        }

        // 只有左边最高的和右边最高的，二者中的较小者比当年的列高，当前列才能接得住水
        for (int i = 1; i <= n - 2; ++i)
            res += max(0, min(leftMaxArr[i], rightMaxArr[i]) - height[i]);
        return res;
    }
};
  • 双指针优化掉 leftMaxArr、rightMaxArr（最优解）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(1)
    int trap(vector<int> &height) {
        int n = height.size();
        int l = 1;
        int r = n - 2;
        // 左边最高
        int lMax = height[0];
        // 右边最高
        int rMax = height[n - 1];

        int res = 0;
        while (l <= r) {
            if (lMax <= rMax) {
                // 左边的最高柱子较低些
                res += max(0, lMax - height[l]);
                lMax = max(lMax, height[l++]);
            } else {
                // 右边的最高柱子较低些
                res += max(0, rMax - height[r]);
                rMax = max(rMax, height[r--]);
            }
        }
        return res;
    }
};
  • 栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int trap(vector<int> &height) {
        int res = 0;
        stack<int> stk;

        for (int i = 0; i < height.size(); i++) {
            // 当前高度大于栈顶高度，说明之前的地方有可能能接水
            // 持续出栈，直到栈顶高度大于等于当前高度或者栈为空
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = height[stk.top()];
                stk.pop();
                if (stk.empty()) break;
                // 两个柱子间的距离，不包含两端
                int distance = i - stk.top() - 1;
                // height[stk.top()] 为左边界，height[i] 为右边界
                int smaller = min(height[stk.top()], height[i]);
                res += distance * (smaller - top);
            }
            stk.emplace(i);
        }
        return res;
    }
};

881. 救生艇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n * logn)，因为有排序，额外空间复杂度 O(1)
    int numRescueBoats(vector<int> &people, int limit) {
        sort(people.begin(), people.end());
        int res = 0;
        for (int l = 0, r = people.size() - 1; l <= r; res++) {
            int sum = l == r ? people[l] : people[l] + people[r];
            // 如果没超重，最轻的可以和最重的共用一条船
            if (sum <= limit) l++;
            r--;
        }
        return res;
    }
};

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(1)
    int maxArea(vector<int> &height) {
        int res = 0;
        for (int l = 0, r = height.size() - 1; l < r;) {
            int water = (r - l) * min(height[l], height[r]);
            res = max(res, water);
            // 每次把短板往中间靠，短板可能变长，总面积才可能变大
            // 如果移动长板，底一定变小，高度不会超过之前的那个短板，高只会原来越低，面积只会变小
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
};

475. 供暖器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 返回当前的地点 houses[i] 由 heaters[j] 来供暖是否是最优
    // 当前的地点 houses[i] 由 heaters[j] 来供暖，产生的半径是a
    // 当前的地点 houses[i] 由 heaters[j + 1] 来供暖，产生的半径是 b
    // 如果 a < b, 说明是最优，供暖不应该跳下一个位置
    // 如果 a >= b, 说明不是最优，应该跳下一个位置
    bool best(vector<int> &houses, vector<int> &heaters, int i, int j) {
        return j == heaters.size() - 1
               || abs(heaters[j] - houses[i]) < abs(heaters[j + 1] - houses[i]);
    }

    // 时间复杂度 O(n * logn)，因为有排序，额外空间复杂度 O(1)
    int findRadius(vector<int> &houses, vector<int> &heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());

        int res = 0;
        // i 号房屋，j 号供暖器
        for (int i = 0, j = 0; i < houses.size(); i++) {
            while (!best(houses, heaters, i, j)) j++;
            res = max(res, abs(heaters[j] - houses[i]));
        }
        return res;
    }
};

41. 缺失的第一个正数

  • 原地映射：把值为 value 的元素映射到数组中下标为 value - 1 的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>

using namespace std;

class Solution {
public:
    // 原地映射：把值为 value 的元素映射到数组中下标为 value-1 的位置
    // 优化了对映射后覆盖掉的值的处理
    int firstMissingPositive(vector<int> &nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            // 如果 nums[i] 也能映射到数组中，并且尚未映射过
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                // 把 nums[i] 映射到 nums[nums[i] - 1]，nums[nums[i] - 1] 放在 nums[i]
                // 然后继续判断新的 nums[i] 是否也需要映射
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        // 遍历寻找第一个空缺
        for (int i = 0; i < n; ++i)
            if (nums[i] != i + 1)
                return i + 1;
        // 重新映射后，数组中没有空缺，说明缺失的第一个正数就是 n + 1
        return n + 1;
    }
};
  • 原地映射：把可以映射到的地方的元素改成负数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <vector>
#include <valarray>

using namespace std;

class Solution {
public:
    // 原地映射：把可以映射到的地方的元素改成负数，映射规则还是 value 映射到 nums[value-1]
    int firstMissingPositive(vector<int> &nums) {
        int n = nums.size();
        // 非正数改成 n + 1
        for (int i = 0; i < n; ++i)
            if (nums[i] <= 0)
                nums[i] = n + 1;

        for (int i = 0; i < n; ++i) {
            // 待映射的值
            int value = abs(nums[i]);
            // 如果可以映射到数组里，就把映射到的地方的元素改成负数
            if (value <= n) nums[value - 1] = -abs(nums[value - 1]);
        }
        for (int i = 0; i < n; ++i)
            if (nums[i] > 0) 
                return i + 1;
        return n + 1;
    }
};
  • 双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <vector>

using namespace std;

class Solution {
public:
    // 时间复杂度 O(n)，额外空间复杂度 O(1)
    int firstMissingPositive(vector<int> &nums) {
        // [0, l) 为已经映射的区域，l 是待处理的位置
        int l = 0;
        // [r, ...) 为无法映射的区域
        // r 的第二个含义是这 r 个数最好的情况下能映射到 [0, r-1]
        // 当有一个数字无法映射的时候，就剩下 r-1 个待映射的，最好情况下能映射到 [0, r-2]
        int r = nums.size();
        // [l, r) 为待映射的区域

        while (l < r) {
            if (nums[l] == l + 1) {
                // 已经映射好了，已映射区域右扩
                l++;
            } else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
                // 把映射不了的数字或者重复出现的数字，与后面待映射的数字交换，无法映射的区域左扩
                // nums[l] <= l 说明 nums[l] 已经映射好了，已经映射的区域中有重复
                // nums[l] > r 说明无法映射
                // nums[nums[l] - 1] == nums[l] 也是说明 nums[l] 已经映射好了，待映射区域中有重复
                swap(nums[l], nums[--r]);
            } else {
                // 可以映射
                swap(nums[l], nums[nums[l] - 1]);
            }
        }
        return l + 1;
    }
};
algorithm, problems
Algorithm Two Pointers
本文由作者按照 CC BY 4.0 进行授权