【高频笔试题】热门基础算法面试题合集（双指针）

站长

2023年07月20日 22:16 · 阅读数 13

本文正在参加「金石计划」

双指针

双指针是基础算法之一，也是笔试面试中的热门考虑知识点，今天通过 666 道面试原题来由浅到深学习「双指针」算法。

1743. 从相邻元素对还原数组

存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。

给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。

题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以按任意顺序出现。

返回原始数组 nums 。如果存在多种解答，返回其中任意一个即可。

示例 1：

输入：adjacentPairs = [[2,1],[3,4],[3,2]]

输出：[1,2,3,4]

解释：数组的所有相邻元素对都在 adjacentPairs 中。
特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。

提示：

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 10510^5105
-10510^5105 <= nums[i], ui, vi <= 10510^5105
题目数据保证存在一些以 adjacentPairs 作为元素对的数组

单向构造（哈希表计数）

根据题意，由于所有的相邻关系都会出现在 numsnumsnums 中，假设其中一个合法数组为 ansansans，长度为 nnn。

那么显然 ans[0]ans[0]ans[0] 和 ans[n−1]ans[n - 1]ans[n−1] 在 numsnumsnums 中只存在一对相邻关系，而其他 ans[i]ans[i]ans[i] 则存在两对相邻关系。

因此我们可以使用「哈希表」对 numsnumsnums 中出现的数值进行计数，找到“出现一次”的数值作为 ansansans 数值的首位，然后根据给定的相邻关系进行「单向构造」，为了方便找到某个数其相邻的数是哪些，我们还需要再开一个「哈希表」记录相邻关系。

代码：

class Solution {
    public int[] restoreArray(int[][] aps) {
        int m = aps.length, n = m + 1;
        Map<Integer, Integer> cnts = new HashMap<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] ap : aps) {
            int a = ap[0], b = ap[1];
            cnts.put(a, cnts.getOrDefault(a, 0) + 1);
            cnts.put(b, cnts.getOrDefault(b, 0) + 1);
            List<Integer> alist = map.getOrDefault(a, new ArrayList<>());
            alist.add(b);
            map.put(a, alist);
            List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
            blist.add(a);
            map.put(b, blist);
        }
        int start = -1;
        for (int i : cnts.keySet()) {
            if (cnts.get(i) == 1) {
                start = i;
                break;
            }
        }
        int[] ans = new int[n];
        ans[0] = start;
        ans[1] = map.get(start).get(0);
        for (int i = 2; i < n; i++) {
            int x = ans[i - 1];
            List<Integer> list = map.get(x);
            for (int j : list) {
                if (j != ans[i - 2]) ans[i] = j;
            }
        }
        return ans;
    }
}

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(n)O(n)O(n)

双向构造（双指针）

在解法一中，我们通过「哈希表」计数得到 ansansans 首位元素作为起点，进行「单向构造」。

那么是否存在使用任意数值作为起点进行的双向构造呢？

答案是显然的，我们可以利用 ansansans 的长度为 2<=n<=1052 <= n <= 10^52<=n<=105，构造一个长度 10610^6106 的数组 qqq（这里可以使用 static 进行加速，让多个测试用例共享一个大数组）。

这里 qqq 数组不一定要开成 1e61e61e6 大小，只要我们 qqq 大小大于 ansansans 的两倍，就不会存在越界问题。

从 qqq 数组的 中间位置 开始，先随便将其中一个元素添加到中间位置，使用「双指针」分别往「两边拓展」（l 和 r 分别指向左右待插入的位置）。

当 l 指针和 r 指针之间已经有 nnn 个数值，说明整个 ansansans 构造完成，我们将 [l+1,r−1][l + 1, r - 1][l+1,r−1] 范围内的数值输出作为答案即可。

代码：

class Solution {
    static int N = (int)1e6+10;
    static int[] q = new int[N];
    public int[] restoreArray(int[][] aps) {
        int m = aps.length, n = m + 1;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] ap : aps) {
            int a = ap[0], b = ap[1];
            List<Integer> alist =  map.getOrDefault(a, new ArrayList<>());
            alist.add(b);
            map.put(a, alist);
            List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
            blist.add(a);
            map.put(b, blist);
        }
        int l = N / 2, r = l + 1;
        int std = aps[0][0];
        List<Integer> list = map.get(std);
        q[l--] = std;
        q[r++] = list.get(0);
        if (list.size() > 1) q[l--] = list.get(1);
        while ((r - 1) - (l + 1) + 1 < n) {
            List<Integer> alist = map.get(q[l + 1]);
            int j = l;
            for (int i : alist) {
                if (i != q[l + 2]) q[j--] = i;
            }
            l = j;

            List<Integer> blist = map.get(q[r - 1]);
            j = r;
            for (int i : blist) {
                if (i != q[r - 2]) q[j++] = i;
            }
            r = j;
        }
        int[] ans = new int[n];
        for (int i = l + 1, idx = 0; idx < n; i++, idx++) {
            ans[idx] = q[i];
        }
        return ans;
    }
}

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(n)O(n)O(n)

2024. 考试的最大困扰度

一位老师正在出一场由 nnn 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是最大化有连续相同结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKeyanswerKeyanswerKey ，其中 answerKey[i]answerKey[i]answerKey[i] 是第 iii 个问题的正确结果。除此以外，还给你一个整数 kkk，表示你能进行以下操作的最多次数：

每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i]answerKey[i]answerKey[i] 改为 'T' 或者 'F' ）。请你返回在不超过 kkk 次操作的情况下，最大连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2

输出：4

解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

提示：

n==answerKey.lengthn == answerKey.lengthn==answerKey.length
1<=n<=5×1041 <= n <= 5 \times 10^41<=n<=5×104
answerKey[i]answerKey[i]answerKey[i] 要么是 'T' ，要么是 'F'
1<=k<=n1 <= k <= n1<=k<=n

滑动窗口

题目求修改次数不超过 kkk 的前提下，连续段 'T' 或 'F' 的最大长度。

等价于求一个包含 'F' 或者 'T' 的个数不超过 kkk 的最大长度窗口。

假定存在一个 int getCnt(char c) 函数，返回包含字符 c 数量不超过 kkk 的最大窗口长度，那么最终 max(getCnt('T'), getCnt('F')) 即是答案。

其中 getCnt 函数的实现可以使用「滑动窗口」：使用 jjj 和 iii 分别代表窗口的左右端点，cntcntcnt 为区间 [j,i][j, i][j,i] 中的字符 c 的数量，每次右端点 iii 移动时，若满足 s[i]=cs[i] = cs[i]=c，让 cntcntcnt 自增，当 cnt>kcnt > kcnt>k 时，使左端点 jjj 往右移动，同时更新 cntcntcnt，直到 [j,i][j, i][j,i] 区间恢复合法性（包含字符 c 的数量 cntcntcnt 不超过 kkk 个）。

代码：

class Solution {
    String s;
    int n, k;
    public int maxConsecutiveAnswers(String answerKey, int _k) {
        s = answerKey;
        n = s.length(); k = _k;
        return Math.max(getCnt('T'), getCnt('F'));
    }
    int getCnt(char c) {
        int ans = 0;
        for (int i = 0, j = 0, cnt = 0; i < n; i++) {
            if (s.charAt(i) == c) cnt++;
            while (cnt > k) {
                if (s.charAt(j) == c) cnt--;
                j++;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1)

1764. 通过连接另一个数组的子数组得到一个数组

给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。

你是否可以从 nums 中选出 n 个不相交的子数组，使得第 i 个子数组与 groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。（也就是说，这些子数组在 nums 中出现的顺序需要与 groups 顺序相同）

如果你可以找出这样的 n 个子数组，请你返回 true ，否则返回 false 。

如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子数组是不相交的。子数组指的是原数组中连续元素组成的一个序列。

示例 1：

输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。

提示：

groups.length == n
1 <= n <= 10310^3103
1 <= groups[i].length, sum(groups[i].length) <= 10310^3103
1 <= nums.length <= 10310^3103
-10710^7107 <= groups[i][j], nums[k] <= 10710^7107

朴素解法

本质上是道模拟题。

使用 i 指针代表 nums 当前枚举到的位置；j 代表 groups 中枚举到哪个数组。

cnt 代表匹配的数组个数。

当 i 开头的连续一段和 groups[j] 匹配：j 指针右移一位（代表匹配下一个数组），i 指针右移 groups[j].length 长度。
当 i 开头的连续一段和 groups[j] 不匹配：i 右移一位。

代码：

class Solution {
    public boolean canChoose(int[][] gs, int[] nums) {
        int n = nums.length, m = gs.length;
        int cnt = 0;
        for (int i = 0, j = 0; i < n && j < m;) {
            if (check(gs[j], nums, i)) {
                i += gs[j++].length;
                cnt++;
            } else {
                i++;
            }
        }
        return cnt == m;
    }
    boolean check(int[] g, int[] nums, int i) {
        int j = 0;
        for (;j < g.length && i < nums.length; j++, i++) {
            if (g[j] != nums[i]) return false;
        }
        return j == g.length;
    }
}

时间复杂度：O(n∗m)O(n * m)O(n∗m)
空间复杂度：O(1)O(1)O(1)

1537. 最大得分

你有两个有序且数组内元素互不相同的数组 nums1 和 nums2 。

一条合法路径定义如下：

选择数组 nums1 或者 nums2 开始遍历（从下标 000 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。

得分定义为合法路径中不同数字的和。

请你返回所有可能合法路径中的最大得分。

由于答案可能很大，请你将它对 109+710^9 + 7109+7 取余后返回。

示例 1：

【高频笔试题】热门基础算法面试题合集（双指针）

输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]

输出：30

解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

提示：

1<=nums1.length<=1051 <= nums1.length <= 10^51<=nums1.length<=105
1<=nums2.length<=1051 <= nums2.length <= 10^51<=nums2.length<=105
1<=nums1[i],nums2[i]<=1071 <= nums1[i], nums2[i] <= 10^71<=nums1[i],nums2[i]<=107
nums1 和 nums2 都是严格递增的数组。

前缀和 + 构造（分段计算）

一个简单且正确的做法，是我们构造一种决策方案，使得能够直接计算出最大得分。

首先，在最佳路径中所有的公共点都必然会经过，因此我们可以将值相等的点进行合并，即看作同一个点。

利用两个数组均满足「单调递增」，我们可以通过 O(n+m)O(n + m)O(n+m) 的复杂度统计出那些公共点，以二元组 (i,j)(i, j)(i,j) 的形式存储到 list 数组（二元组含义为 nums1[i]=nums2[j]nums1[i] = nums2[j]nums1[i]=nums2[j]）。

对于 list 中的每对相邻元素（相邻公共点），假设为 (ai,bi)(a_i, b_i)(ai,bi) 和 (ci,di)(c_i, d_i)(ci,di)，我们可以通过「前缀和」计算出 nums1[ai...ci]nums1[a_i ... c_i]nums1[ai...ci] 以及 nums2[bi...di]nums2[b_i ... d_i]nums2[bi...di] 的和，从而决策出在 nums1[ai]nums1[a_i]nums1[ai]（或者说是 nums2[bi]nums2[b_i]nums2[bi]，这两个是同一个点）时，我们应当走哪一段。

当计算完所有公共点之间的得分后，对于最佳路线的首位两端，也是结合「前缀和」做同样的逻辑处理即可。

代码：

class Solution {
    int MOD = (int)1e9 + 7;
    public int maxSum(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        long[] s1 = new long[n + 10], s2 = new long[m + 10];
        for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums1[i - 1];
        for (int i = 1; i <= m; i++) s2[i] = s2[i - 1] + nums2[i - 1];
        List<int[]> list = new ArrayList<>();
        for (int i = 0, j = 0; i < n && j < m; ) {
            if (nums1[i] == nums2[j]) list.add(new int[]{i, j});
            if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        long ans = 0;
        for (int i = 0, p1 = -1, p2 = -1; i <= list.size(); i++) {
            int idx1 = 0, idx2 = 0;
            if (i < list.size()) {
                int[] info = list.get(i);
                idx1 = info[0]; idx2 = info[1];
            } else {
                idx1 = n - 1; idx2 = m - 1;
            }
            long t1 = s1[idx1 + 1] - s1[p1 + 1], t2 = s2[idx2 + 1] - s2[p2 + 1];
            ans += Math.max(t1, t2);
            p1 = idx1; p2 = idx2;
        }
        return (int)(ans % MOD);
    }
}

时间复杂度：O(n+m)O(n + m)O(n+m)
空间复杂度：O(n+m)O(n + m)O(n+m)

序列 DP

另外一个较为常见的做法是「序列 DP」做法。

定义 f[i]f[i]f[i] 代表在 nums1 上进行移动，到达 nums1[i]nums1[i]nums1[i] 的最大得分；定义 g[j]g[j]g[j] 代表在 nums2 上进行移动，到达 nums[j]nums[j]nums[j] 的最大得分。

由于两者的分析是类似的，我们以 f[i]f[i]f[i] 为例进行分析即可。

不失一般性考虑 f[i]f[i]f[i] 如何转移，假设当前处理到的是 nums1[i]nums1[i]nums1[i]，根据 nums1[i]nums1[i]nums1[i] 是否为公共点，进行分情况讨论：

nums1[i]nums1[i]nums1[i] 不为公共点，此时只能由 nums[i−1]nums[i - 1]nums[i−1] 转移而来，即有 f[i]=f[i−1]+nums[i]f[i] = f[i - 1] + nums[i]f[i]=f[i−1]+nums[i]；
nums1[i]nums1[i]nums1[i] 为公共点（假设与 nums2[j]nums2[j]nums2[j] 公共），此时能够从 nums1[i−1]nums1[i - 1]nums1[i−1] 或 nums2[j−1]nums2[j - 1]nums2[j−1] 转移而来，我们需要取 f[i−1]f[i - 1]f[i−1] 和 g[j−1]g[j - 1]g[j−1] 的最大值，即有 f[i]=g[j]=max⁡(f[i−1],g[j−1])+nums1[i]f[i] = g[j] = \max(f[i - 1], g[j - 1]) + nums1[i]f[i]=g[j]=max(f[i−1],g[j−1])+nums1[i]。

更重要的是，我们需要确保计算 f[i]f[i]f[i] 时，g[j−1]g[j - 1]g[j−1] 已被计算完成。

由于最佳路线必然满足「单调递增」，因此我们可以使用「双指针」来对 f[i]f[i]f[i] 和 g[j]g[j]g[j] 同时进行转移，每次取值小的进行更新，从而确保更新过程也是单调的，即当需要计算 f[i]f[i]f[i] 时，比 nums1[i]nums1[i]nums1[i] 小的 f[X]f[X]f[X] 和 g[X]g[X]g[X] 均被转移完成。

代码：

class Solution {
    int MOD = (int)1e9 + 7;
    public int maxSum(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        long[] f = new long[n + 1], g = new long[m + 1];
        int i = 1, j = 1;
        while (i <= n || j <= m) {
            if (i <= n && j <= m) {
                if (nums1[i - 1] < nums2[j - 1]) {
                    f[i] = f[i - 1] + nums1[i - 1];
                    i++;
                } else if (nums2[j - 1] < nums1[i - 1]) {
                    g[j] = g[j - 1] + nums2[j - 1];
                    j++;
                } else {
                    f[i] = g[j] = Math.max(f[i - 1], g[j - 1]) + nums1[i - 1];
                    i++; j++;
                }
            } else if (i <= n) {
                f[i] = f[i - 1] + nums1[i - 1];
                i++;
            } else {
                g[j] = g[j - 1] + nums2[j - 1];
                j++;
            }
        }
        return (int) (Math.max(f[n], g[m]) % MOD);
    }
}

时间复杂度：O(n+m)O(n + m)O(n+m)
空间复杂度：O(n+m)O(n + m)O(n+m)

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]

输出：5

解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

提示：

1<=nums.length<=1041 <= nums.length <= 10^41<=nums.length<=104
−105<=nums[i]<=105-10^5 <= nums[i] <= 10^5−105<=nums[i]<=105
进阶：你可以设计一个时间复杂度为 O(n)O(n)O(n) 的解决方案吗？

双指针 + 排序

最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针 iii 和 jjj 分别找到左右两端第一个不同的地方，那么 [i,j][i, j][i,j] 这一区间即是答案。

代码：

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

时间复杂度：O(nlog⁡n)O(n\log{n})O(nlogn)
空间复杂度：O(n)O(n)O(n)

双指针 + 线性扫描

另外一个做法是，我们把整个数组分成三段处理。

起始时，先通过双指针 iii 和 jjj 找到左右两次侧满足 单调递增 的分割点。

即此时 [0,i][0, i][0,i] 和 [j,n)[j, n)[j,n) 满足升序要求，而中间部分 (i,j)(i, j)(i,j) 不确保有序。

然后我们对中间部分 [i,j][i, j][i,j] 进行遍历：

发现 nums[x]<nums[i−1]nums[x] < nums[i - 1]nums[x]<nums[i−1]：由于对 [i,j][i, j][i,j] 部分进行排序后 nums[x]nums[x]nums[x] 会出现在 nums[i−1]nums[i - 1]nums[i−1] 后，将不满足整体升序，此时我们需要调整分割点 iii 的位置；
发现 nums[x]>nums[j+1]nums[x] > nums[j + 1]nums[x]>nums[j+1]：由于对 [i,j][i, j][i,j] 部分进行排序后 nums[x]nums[x]nums[x] 会出现在 nums[j+1]nums[j + 1]nums[j+1] 前，将不满足整体升序，此时我们需要调整分割点 jjj 的位置。

一些细节：在调整 iii 和 jjj 的时候，我们可能会到达数组边缘，这时候可以建立两个哨兵：数组左边存在一个足够小的数，数组右边存在一个足够大的数。

代码：

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int u = l; u <= r; u++) {
            if (nums[u] < min) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[j] < nums[u]) j++;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j == i ? 0 : (j - 1) - (i + 1) + 1;
    }
}

时间复杂度：O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1)

2000. 反转单词前缀

给你一个下标从 000 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ，反转 word 中从下标 000 开始、直到下标 i 结束（含下标 i ）的那段字符。如果 word 中不存在字符 ch ，则无需进行任何操作。

例如，如果 word = "abcdefd" 且 ch = "d" ，那么你应该反转从下标 000 开始、直到下标 3 结束（含下标 3 ）。结果字符串将会是 "dcbaefd" 。

返回结果字符串。

示例 1：

输入：word = "abcdefd", ch = "d"

输出："dcbaefd"

解释："d" 第一次出现在下标 3 。 
反转从下标 0 到下标 3（含下标 3）的这段字符，结果字符串是 "dcbaefd" 。

提示：

1<=word.length<=2501 <= word.length <= 2501<=word.length<=250
word 由小写英文字母组成
ch 是一个小写英文字母

模拟

先从前往后遍历，找到第一个 ch 的下标 idxidxidx（初始值为 −1-1−1），然后对 [0,idx][0, idx][0,idx] 应用双指针进行翻转（若没有 ch 字符，则 idx=−1idx = -1idx=−1，则 [0,idx][0, idx][0,idx] 为不合法区间，翻转过程被跳过）。

代码：

class Solution {
    public String reversePrefix(String word, char ch) {
        char[] cs = word.toCharArray();
        int n = cs.length, idx = -1;
        for (int i = 0; i < n && idx == -1; i++) {
            if (cs[i] == ch) idx = i;
        }
        int l = 0, r = idx;
        while (l < r) {
            char c = cs[l];
            cs[l++] = cs[r];
            cs[r--] = c;
        }
        return String.valueOf(cs);
    }
}

时间复杂度：O(n)O(n)O(n)
空间复杂度：toCharArray 会产生新数组，复杂度为 O(n)O(n)O(n)

总结

双指针算法常见于「链表」类题目，或是运用到「滑动窗口」。

通常使用「双指针」求解的题目都均由“线性复杂度”，这引导我们当题目数据范围在 104−10510^4 - 10^5104−105 时候，并且没有思路是，可以往「双指针」方向去思考。