罗罗编程学习记录
本页内容 展开查看

02.2.1.4 二维矩阵与排序配合双指针

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.1 数组与双指针滑窗

02.2.1.4-001 二维矩阵在内存中怎么存?遍历顺序影响什么?

一句话结论

Java 二维数组是数组的数组,每行一个连续数组,行间引用跳转;按行遍历地址连续、缓存友好,按列遍历跨行跳转、缓存表现差。

概念解释

  • 行优先:行内元素连续。
  • 列遍历:每次跳到下一行同列。
  • 局部性差异影响实测速度。

原理流程

  1. 确认行列规模。
  2. 热循环按行优先访问。
  3. 必须按列处理时评估缓存代价。

代码 / 示例

for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        use(a[i][j]);          // 行优先,连续

常见误区

  • 误区:二维数组是一块连续大内存;正解:每行独立分配,行首是引用。
  • 误区:行列遍历速度相同;正解:列遍历缓存失效率更高。

追问

  • Q:矩阵转置复杂度? A:O(mn),逐个交换位置。
  • Q:不规则矩阵(每行长度不同)? A:先取每行长度,不能假设 n 一致。

02.2.1.4-002 旋转图像(LC 48)原地怎么转 90 度?

一句话结论

先上下翻转(或主对角线转置),再沿另一对角线翻转;两步组合等价顺时针 90 度;原地 O(n²) 时间 O(1) 空间。

概念解释

  • 转置:a[i][j] 与 a[j][i] 交换。
  • 行反转:每行左右翻转。
  • 组合得到顺时针旋转。

原理流程

  1. 主对角线转置。
  2. 每行水平反转。
  3. 核对四角映射。

代码 / 示例

public void rotate(int[][] a) {
    int n = a.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;
        }
    for (int[] row : a) reverse(row);
}
void reverse(int[] row) {
    int l = 0, r = row.length - 1;
    while (l < r) { int t = row[l]; row[l++] = row[r]; row[r--] = t; }
}

常见误区

  • 误区:一步直接按映射写循环;正解:分步翻转更不易错,映射关系要核对。
  • 误区:非方阵也套用;正解:题目为 n×n 方阵,矩形旋转需另开空间。

追问

  • Q:逆时针 90 怎么改? A:反转顺序或改翻转方向。
  • Q:不开原地怎么做? A:新矩阵 b[j][n-1-i]=a[i][j]。

02.2.1.4-003 螺旋矩阵(LC 54)怎么遍历?

一句话结论

维护上下左右四个边界,按右、下、左、上顺序逐层收缩;每走完一边收缩对应边界,并在每次移动前检查边界是否相交;O(mn) 时间。

概念解释

  • 边界:top、bottom、left、right。
  • 方向循环:右行 → 下列 → 左行 → 上列。
  • 收缩后可能剩一行或一列,需检查边界。

原理流程

  1. 初始化四边界。
  2. 右行后 top++;下列后 right--。
  3. 左行前检查 top≤bottom;上行前检查 left≤right。
  4. 直到边界相交。

代码 / 示例

public List<Integer> spiralOrder(int[][] a) {
    List<Integer> res = new ArrayList<>();
    int t = 0, b = a.length - 1, l = 0, r = a[0].length - 1;
    while (t <= b && l <= r) {
        for (int j = l; j <= r; j++) res.add(a[t][j]);
        t++;
        for (int i = t; i <= b; i++) res.add(a[i][r]);
        r--;
        if (t <= b) for (int j = r; j >= l; j--) res.add(a[b][j]);
        b--;
        if (l <= r) for (int i = b; i >= t; i--) res.add(a[i][l]);
        l++;
    }
    return res;
}

常见误区

  • 误区:左行/上行前不检查边界;正解:可能只剩一行/一列,重复遍历。
  • 误区:边界收缩顺序错位;正解:走完一边才收缩对应边界。

追问

  • Q:单行矩阵输出什么? A:只走右行,其余方向被边界检查跳过。
  • Q:螺旋遍历能用递归吗? A:可以按层递归,空间 O(min(m,n))。

02.2.1.4-004 螺旋矩阵 II(LC 59)怎么生成?

一句话结论

与遍历同构:四边界逐层向内,按顺序填入递增数字;O(n²) 时间 O(n²) 结果空间。

概念解释

  • 填充顺序与遍历一致。
  • 数字从 1 递增到 n²。
  • 边界收缩规则相同。

原理流程

  1. 开 n×n 矩阵。
  2. 四边循环填数并收缩。
  3. 检查边界避免重复填。

代码 / 示例

public int[][] generateMatrix(int n) {
    int[][] a = new int[n][n];
    int t = 0, b = n - 1, l = 0, r = n - 1, num = 1;
    while (t <= b && l <= r) {
        for (int j = l; j <= r; j++) a[t][j] = num++;
        t++;
        for (int i = t; i <= b; i++) a[i][r] = num++;
        r--;
        if (t <= b) for (int j = r; j >= l; j--) a[b][j] = num++;
        b--;
        if (l <= r) for (int i = b; i >= t; i--) a[i][l] = num++;
        l++;
    }
    return a;
}

常见误区

  • 误区:数字填完边界不收缩;正解:每层填完必须收缩。
  • 误区:奇数 n 中心格漏填;正解:最后一层单行/单列由边界检查覆盖。

追问

  • Q:n=1? A:直接填中心格 1。
  • Q:生成矩形 m×n? A:边界按 m、n 分别维护。

02.2.1.4-005 矩阵置零(LC 73)怎么做?

一句话结论

要求原地时用首行首列记录哪些行/列要置零,先记录再按标记清零;单独标记首行首列本身是否需要清零;O(mn) 时间 O(1) 额外空间。

概念解释

  • 标记位:a[i][0] 记第 i 行,a[0][j] 记第 j 列。
  • 首行首列自身需额外布尔记录。
  • 先标记后清零,避免标记被覆盖。

原理流程

  1. 记录首行、首列是否含零。
  2. 用内部格扫描,标记到首行首列。
  3. 按标记清内部行列。
  4. 最后处理首行首列。

代码 / 示例

public void setZeroes(int[][] a) {
    int m = a.length, n = a[0].length;
    boolean row0 = false, col0 = false;
    for (int j = 0; j < n; j++) if (a[0][j] == 0) row0 = true;
    for (int i = 0; i < m; i++) if (a[i][0] == 0) col0 = true;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
    if (row0) for (int j = 0; j < n; j++) a[0][j] = 0;
    if (col0) for (int i = 0; i < m; i++) a[i][0] = 0;
}

常见误区

  • 误区:遇到零立刻清行清列;正解:会破坏后续扫描依据,必须先标记。
  • 误区:首行首列标记位与自身混淆;正解:单独布尔记录。

追问

  • Q:非原地做法? A:两个布尔数组记录行列,O(m+n) 空间。
  • Q:标记位用 -1 可以吗? A:值域允许时可行,最后统一转零。

02.2.1.4-006 对角线遍历(LC 498)怎么控制方向?

一句话结论

按对角线编号遍历,方向在右上与左下之间切换;碰到边界换向并调整下一起点;O(mn) 时间 O(1) 额外空间。

概念解释

  • 对角线:i+j 为定值。
  • 方向:右上 i--, j++ 或左下 i++, j--。
  • 边界换向:触顶/触右/触底/触左。

原理流程

  1. 起点 (0,0),方向右上。
  2. 沿对角线走,出界时按边界调整起点。
  3. 切换方向继续。

代码 / 示例

public int[] findDiagonalOrder(int[][] a) {
    int m = a.length, n = a[0].length;
    int[] res = new int[m * n];
    int i = 0, j = 0, up = 1;
    for (int k = 0; k < res.length; k++) {
        res[k] = a[i][j];
        if (up == 1) {
            if (j == n - 1) { i++; up = -1; }
            else if (i == 0) { j++; up = -1; }
            else { i--; j++; }
        } else {
            if (i == m - 1) { j++; up = 1; }
            else if (j == 0) { i++; up = 1; }
            else { i++; j--; }
        }
    }
    return res;
}

常见误区

  • 误区:边界换向顺序写反;正解:先判右边界再判上边界,避免越界。
  • 误区:方向切换后起点错位;正解:按出界方向回退到合法起点。

追问

  • Q:矩形不对称时? A:边界判断分别按 m、n 处理。
  • Q:对角线求和类问题? A:按 i+j 或 i-j 分组。

02.2.1.4-007 搜索二维矩阵(LC 74)怎么二分?

一句话结论

矩阵每行有序且下一行首元素 ≥ 上一行尾元素,可视为拉长的一维有序数组;下标 mid 映射到 (mid/n, mid%n),二分 O(log(mn))。

概念解释

  • 全局有序:行内有序 + 行间递增。
  • 一维映射:折半下标换算行列。
  • 前提:行间严格满足有序条件。

原理流程

  1. 低 0,高 m·n-1。
  2. mid 换算行列取值比较。
  3. 收缩二分区间。

代码 / 示例

public boolean searchMatrix(int[][] a, int t) {
    int m = a.length, n = a[0].length;
    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int v = a[mid / n][mid % n];
        if (v == t) return true;
        if (v < t) l = mid + 1; else r = mid - 1;
    }
    return false;
}

常见误区

  • 误区:不满足行间有序也套一维二分;正解:LC 240 行列分别有序但全局无序,需另一策略。
  • 误区:mid 映射行列写反;正解:行 = mid/n,列 = mid%n。

追问

  • Q:两次二分做法? A:先二分定位行,再二分定位列,O(log m + log n)。
  • Q:矩阵为空? A:入口判空返回 false。

02.2.1.4-008 有序矩阵查找(LC 240)为什么从右上角走?

一句话结论

行列分别有序但全局无序时,从右上角出发:当前值大则左移,小则下移;每步排除一行或一列,O(m+n) 时间 O(1) 空间。

概念解释

  • 右上角:左小下大。
  • 比较后方向唯一:大往左,小往下。
  • 不重复排除行列。

原理流程

  1. 起点 (0, n-1)。
  2. 等于返回;大于目标左移;小于目标下移。
  3. 出界未命中返回 false。

代码 / 示例

public boolean searchMatrix(int[][] a, int t) {
    int i = 0, j = a[0].length - 1;
    while (i < a.length && j >= 0) {
        if (a[i][j] == t) return true;
        if (a[i][j] > t) j--; else i++;
    }
    return false;
}

常见误区

  • 误区:从左上角开始;正解:左上角右大下也大,方向不唯一。
  • 误区:套用一维二分;正解:全局无序,二分不成立。

追问

  • Q:左下角对称策略? A:当前值大上移,小右移,同样 O(m+n)。
  • Q:最坏走多少步? A:从一角到对角,m+n 步。

02.2.1.4-009 矩阵转置怎么写?

一句话结论

b[j][i] = a[i][j],m×n 转置为 n×m;非方阵必须新开结果矩阵;O(mn) 时间 O(mn) 结果空间。

概念解释

  • 行列互换。
  • 方阵可原地交换上三角。
  • 非方阵尺寸变化,不能原地。

原理流程

  1. 按新尺寸开矩阵。
  2. 逐格映射。
  3. 核对行列下标。

代码 / 示例

public int[][] transpose(int[][] a) {
    int m = a.length, n = a[0].length;
    int[][] b = new int[n][m];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) b[j][i] = a[i][j];
    return b;
}

常见误区

  • 误区:非方阵原地转置;正解:尺寸不同必须新开。
  • 误区:下标映射写反;正解:新行 = 旧列,新列 = 旧行。

追问

  • Q:方阵原地转置? A:只遍历上三角交换 a[i][j] 与 a[j][i]。
  • Q:转置与旋转关系? A:转置加行反转得到 90 度旋转。

02.2.1.4-010 三数之和(LC 15)怎么做?

一句话结论

排序后固定一个数 i,内层相向双指针找两数之和为 -a[i];命中后两侧跳过重复;时间 O(n²),空间 O(排序栈/结果)。

概念解释

  • 排序使内层可双指针。
  • 固定点枚举,内层夹逼。
  • 去重在固定点与命中处。

原理流程

  1. 排序。
  2. i 枚举,跳过重复。
  3. l=i+1,r=n-1,按和移动。
  4. 命中记录并跳重复。

代码 / 示例

public List<List<Integer>> threeSum(int[] a) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(a);
    for (int i = 0; i < a.length - 2; i++) {
        if (a[i] > 0) break;
        if (i > 0 && a[i] == a[i - 1]) continue;
        int l = i + 1, r = a.length - 1;
        while (l < r) {
            int s = a[i] + a[l] + a[r];
            if (s == 0) {
                res.add(Arrays.asList(a[i], a[l], a[r]));
                while (l < r && a[l] == a[l + 1]) l++;
                while (l < r && a[r] == a[r - 1]) r--;
                l++; r--;
            } else if (s < 0) l++; else r--;
        }
    }
    return res;
}

常见误区

  • 误区:固定点不跳重复;正解:相同 i 会产生重复三元组。
  • 误区:命中后只移一侧;正解:两侧都要移动并跳重复。

追问

  • Q:为什么 a[i] > 0 可 break? A:排序后后续更大,三数之和不可能为 0。
  • Q:哈希做法可行吗? A:可行但去重麻烦,排序双指针更直观。

02.2.1.4-011 最接近的三数之和(LC 16)怎么做?

一句话结论

排序 + 固定点 + 双指针,维护与 target 差值绝对值最小的组合;和偏小移 l,偏大移 r;O(n²) 时间。

概念解释

  • 目标不是等于,而是差值最小。
  • 每次比较更新最近答案。
  • 命中差值 0 可直接返回。

原理流程

  1. 排序。
  2. 固定 i,双指针夹逼。
  3. 比较当前和与最近差值。
  4. 按和值移动指针。

代码 / 示例

public int threeSumClosest(int[] a, int target) {
    Arrays.sort(a);
    int best = a[0] + a[1] + a[2];
    for (int i = 0; i < a.length - 2; i++) {
        int l = i + 1, r = a.length - 1;
        while (l < r) {
            int sum = a[i] + a[l] + a[r];
            if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
            if (sum == target) return sum;
            if (sum < target) l++; else r--;
        }
    }
    return best;
}

常见误区

  • 误区:记录差值符号而不是绝对值;正解:比较距离用绝对值。
  • 误区:初始 best 未初始化;正解:取前三个元素作为初值。

追问

  • Q:差值相同怎么选? A:按题目口径,通常保留先遇到的即可。
  • Q:能剪枝吗? A:固定点段和明显偏离时可提前判断。

02.2.1.4-012 四数之和(LC 18)怎么扩展?

一句话结论

两层枚举固定两个数,内层双指针找另两个;外层跳过重复,必要时按范围剪枝;O(n³) 时间,去重逻辑与三数之和一致。

概念解释

  • 外层 i、j 两层。
  • 内层 l、r 双指针。
  • 重复在每层枚举点跳过。

原理流程

  1. 排序。
  2. i、j 枚举并跳重复。
  3. 内层夹逼,命中跳重复。
  4. 越界范围剪枝。

代码 / 示例

public List<List<Integer>> fourSum(int[] a, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(a);
    int n = a.length;
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && a[i] == a[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && a[j] == a[j - 1]) continue;
            int l = j + 1, r = n - 1;
            while (l < r) {
                long sum = (long) a[i] + a[j] + a[l] + a[r];
                if (sum == target) {
                    res.add(Arrays.asList(a[i], a[j], a[l], a[r]));
                    while (l < r && a[l] == a[l + 1]) l++;
                    while (l < r && a[r] == a[r - 1]) r--;
                    l++; r--;
                } else if (sum < target) l++; else r--;
            }
        }
    }
    return res;
}

常见误区

  • 误区:四数相加 int 溢出;正解:用 long 计算和再比较。
  • 误区:只在最内层去重;正解:外层 i、j 都要跳重复。

追问

  • Q:K 数之和通用思路? A:递归降维到两数之和,配合排序双指针。
  • Q:剪枝怎么做? A:当前层最小/最大和与 target 比较,提前 break/continue。

02.2.1.4-013 三数之和的去重细节有哪些?

一句话结论

固定点与上一值相同则跳过;命中解后左右指针分别跳过相邻重复;排序是去重前提,保证重复值相邻。

概念解释

  • 外层去重:避免相同首元素重复展开。
  • 内层去重:避免相同第二、三元素重复收集。
  • 顺序:先记录再跳重复。

原理流程

  1. 排序后重复相邻。
  2. 外层 a[i]==a[i-1] 跳过。
  3. 命中后 while 跳过相邻相等。

代码 / 图示

if (i > 0 && a[i] == a[i - 1]) continue;
while (l < r && a[l] == a[l + 1]) l++;
while (l < r && a[r] == a[r - 1]) r--;

常见误区

  • 误区:用结果集合判重代替相邻跳过;正解:排序后相邻跳过更高效。
  • 误区:跳重复时越界;正解:while 条件带 l<r。

追问

  • Q:不排序怎么去重? A:把组合序列化入哈希集合判重。
  • Q:重复元素参与计数吗? A:本题要不重复组合,跳过;计数题另算。

02.2.1.4-014 区间合并(LC 56)怎么做?

一句话结论

按区间左端点排序,遍历中当前区间与结果末段重叠则合并右端点,不重叠则新增;O(n log n) 排序 + O(n) 扫描。

概念解释

  • 排序后区间按起点相邻。
  • 重叠判断:当前起点 ≤ 末段终点。
  • 合并取右端点较大值。

原理流程

  1. 按起点排序。
  2. 首段入结果。
  3. 逐段比较重叠,合并或追加。

代码 / 示例

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
    List<int[]> res = new ArrayList<>();
    for (int[] cur : intervals) {
        if (res.isEmpty() || res.get(res.size() - 1)[1] < cur[0]) res.add(cur);
        else res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], cur[1]);
    }
    return res.toArray(new int[0][]);
}

常见误区

  • 误区:按右端点排序;正解:按左端点排序才能顺序合并。
  • 误区:重叠判断用严格小于;正解:端点相接(等于)也算合并。

追问

  • Q:插入区间(LC 57)思路? A:先加左侧不重叠段,合并重叠段,再加右侧。
  • Q:合并后区间有序吗? A:按起点升序。

02.2.1.4-015 排序配合双指针的通用前提是什么?

一句话结论

题目不要求保留原顺序,且内层匹配可由大小比较决定方向;排序预处理 O(n log n) 后,内层可双指针 O(n);需保留下标时不能直接排序。

概念解释

  • 前提:可重排。
  • 收益:内层枚举降为线性。
  • 代价:排序时间与稳定性。

原理流程

  1. 确认输出不依赖原下标。
  2. 排序获得有序性。
  3. 外层枚举 + 内层双指针。

代码 / 图示

可排序:三数之和、区间合并
不可排序:要求返回原下标、相对顺序敏感

常见误区

  • 误区:返回原下标还排序;正解:需保留下标映射。
  • 误区:排序代价不计入;正解:整体复杂度含 O(n log n)。

追问

  • Q:稳定排序有必要吗? A:仅当次级顺序敏感时关注稳定性。
  • Q:排序后双指针为什么不回退? A:有序性使移动方向唯一。

02.2.1.4-016 矩阵遍历类问题的边界用例有哪些?

一句话结论

空矩阵、单行、单列、方阵、矩形不对称、单元素;验证边界收缩、换向与下标不越界。

概念解释

  • 退化维度:行或列为 1。
  • 不对称:m ≠ n。
  • 空:入口判空。

原理流程

  1. 先判 null 与长度 0。
  2. 构造单行/单列用例。
  3. 走查边界变化。

代码 / 图示

[] / [[]] / 1×n / m×1 / n×n
矩形 m≠n

常见误区

  • 误区:默认矩阵至少两行两列;正解:退化维度必须处理。
  • 误区:访问 a[0][0] 前不判空;正解:先校验行与列存在。

追问

  • Q:螺旋矩阵单行输出顺序? A:从左到右一行。
  • Q:列遍历空列? A:列数为 0 时直接返回。

02.2.1.4-017 矩阵原地修改需要注意什么?

一句话结论

原地修改前确认题目允许覆盖;标记位方案要区分记录区与数据区;避免边扫描边清零破坏后续判断;必要时用布尔数组做非原地标记。

概念解释

  • 可改性:题面是否允许改输入。
  • 标记覆盖:记录位不能被中途清掉。
  • 非原地备选:行列布尔数组。

原理流程

  1. 确认允许原地。
  2. 分离标记阶段与清零阶段。
  3. 边界行列单独记录。

代码 / 图示

阶段一:扫描记录标记
阶段二:按标记修改
不要在扫描中立即清零

常见误区

  • 误区:标记与清零同一遍完成;正解:会把后续扫描依据清掉。
  • 误区:原地方案影响其他调用方;正解:引用传递下原矩阵被改。

追问

  • Q:标记位占用数据值怎么办? A:用额外布尔数组,或值域允许时用特殊标记。
  • Q:旋转是原地吗? A:方阵可原地翻转组合;矩形需新开。

02.2.1.4-018 二维问题的复杂度怎么算?

一句话结论

矩阵规模 m×n,遍历一格 O(1),整体 O(mn);辅助空间按标记结构规模算;排序类按元素数 n 计 O(n log n)。

概念解释

  • 时间:格数 × 单格代价。
  • 空间:标记数组/结果矩阵。
  • 行列规模分别标注。

原理流程

  1. 统计访问格数。
  2. 单格操作量级。
  3. 辅助结构规模。

代码 / 图示

遍历矩阵:O(mn)
标记位原地:O(1) 额外
布尔行列:O(m+n)

常见误区

  • 误区:把 m、n 混为一个 n;正解:标注 O(mn),空间按 m/n 分别说。
  • 误区:结果矩阵计入辅助空间;正解:输出空间按题面口径单列。

追问

  • Q:二分查找矩阵复杂度? A:O(log(mn)),不是 O(m+n)。
  • Q:右上角走路复杂度? A:O(m+n),每步排除一行或一列。

02.2.1.4-019 矩阵中哪些信息可以提前排序利用?

一句话结论

区间起止、元素配对、可脱离位置的统计量可排序;依赖行列位置、相邻关系、原下标的信息不能排序;排序前先判断输出是否要求保序。

概念解释

  • 可排序:区间端点、数值配对。
  • 不可排序:网格邻接、路径、原下标。
  • 保序要求决定可行性。

原理流程

  1. 列出输出依赖的信息。
  2. 判断位置信息是否必须保留。
  3. 可排序则排序后双指针。

代码 / 图示

区间合并:端点可排序
路径/邻接:位置敏感,不可排序
原下标:需带下标一起排序

常见误区

  • 误区:数值题一律先排序;正解:位置相关问题排序会破坏结构。
  • 误区:排序后丢掉原下标;正解:需要时下标随元素一起携带。

追问

  • Q:两数之和要求原下标? A:用哈希保留下标,不排序。
  • Q:排序后如何回溯原位置? A:元素打包成 (值, 原下标) 再排序。

02.2.1.4-020 数组/矩阵题如何从暴力优化到双指针?

一句话结论

暴力枚举所有组合是 O(n²);若排序后大小关系能唯一决定指针移动方向,内层枚举降为线性扫描;先证明移动方向不会漏解,再落地双指针。

概念解释

  • 暴力:枚举所有对/三元组。
  • 有序性:比较即可排除一侧。
  • 不漏解:移动方向由单调性保证。

原理流程

  1. 写暴力枚举基线。
  2. 观察有序后和值变化方向。
  3. 双指针单向收敛,计入排序代价。

代码 / 图示

暴力三数:O(n³)
排序 + 固定 + 双指针:O(n log n) + O(n²)

常见误区

  • 误区:未证明不漏解就移指针;正解:先说明为何移动一侧不会错过答案。
  • 误区:优化后忘记排序复杂度;正解:整体取高阶。

追问

  • Q:什么情况双指针不能替代内层枚举? A:无序且不能排序、或匹配条件非大小比较。
  • Q:双指针空间收益? A:O(1) 额外空间,对比内层哈希。