双指针 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 ❓ 双层 `while` 循环，什么时候 `i` 和 `j` 的更新放前面，什么时候 `i` 和 `j` 的更新放后面？ 取决于 i 和 j 的含义： - 如果 `i` 或 `j` 指向 "**当前待处理位置**"，那么在循环体的尾部，完成对当前位置的处理后，就需要移动 i 和 j，使其指向下一个待处理位置； - 如果 `i` 或 `j` 表示 "**当前待处理区间的左开/右开边界**"，例如 `[l, r)` 或者 `(l, r]`，则作为 "**开区间的边界**" 时其本身就已经指向了 "待处理位置"，因此在循环体的末尾通常不需要再移动。 ❓滑动窗口和双指针有什么关系？ - 滑动窗口是**双指针法**的一种情况，**两指针代表左右边界**，包括： - 定长滑动窗口（窗口大小、即两指针相对距离不变） - **变长滑动窗口**（在单调性序列上，**枚举各个位置作为区间==右边界==**） #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** ❓ 那些变长滑动窗口的模版题，如果按 "枚举左边界" 去写是否好理解？ 不好理解。 # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 双指针模版参见 [[00-数据结构与算法笔记/专题总结/双指针模版.canvas|双指针模版]] ![[00-数据结构与算法笔记/专题总结/双指针模版.canvas|双指针模版]] # 双指针（尺取法）总结 > 双指针法，也称 "**尺取法**"。两个指针的组合实际上有 $n^2$ 种情况，双指针核心思想是**在扫描上做优化**，将**两层循环优化到只需 $O(2n)$ 的遍历**。 "双指针" 法是一个统称，**在不同场景下具体应用方式不同**，常见的包括： - 双指针——**位置处理**：每次 **==提取==**/处理 **==指针所指的两个位置==**； - 双指针——**区间提取/区间确认**：每次提取/处理**一个或两个区间**； - 双指针——**主次指针（辅助指针）**："主指针" **枚举/遍历**各个位置，**==辅助指针==** 视情况移动； - 双指针——**滑动窗口**：本质上是在 **==单调性==序列**上 **==枚举==各个==右边界==** 对应的窗口情况 - 双指针——**快慢指针**：两个指针**步数不同**，常用于 "环" 相关问题； ### 双指针「位置处理」、「确认区间」、「滑动窗口」的区别 #### 找位置 ![[Excalidraw-Solution/双指针_0.excalidraw.svg|400]] %% [[Excalidraw-Solution/双指针_0.excalidraw.md|🖋 Edit in Excalidraw]] %% #### 找区间「**找区间/确认区间**」是每次要搜索/确定一个 "**==最大化==的、==右边界不可再延伸==**" **的目标区间段**。 - **不同区间之间通常是 ==无重叠的==**，没有 "滑动" 的过程，每确定一段**极大区间**后才进行处理，而后从 **==剩余未搜索区域==** 中找下一个所需区间； - 外层循环逻辑：从**剩余未搜索区域**中找到**满足条件的起始点**作为 **==左边界==** 固定, 而后**扩展==右边界==** 直到**不满足条件**，从而确定一个**目标区间**。 ![[Excalidraw-Solution/双指针_1.excalidraw.svg|400]] %%[[Excalidraw-Solution/双指针_1.excalidraw.md|🖋 Edit in Excalidraw]]%% #### 滑动窗口「**滑动窗口**」本质上是枚举所有位置作为 "右边界" 的情况，因此**窗口右边界每次==只移动一步==**， "**整个窗口**" 通过 **==滑动 or 扩展/收缩==** 进行搜索，**窗口在变化前后==具有重叠的覆盖区域**。 ![[Excalidraw-Solution/双指针_2.excalidraw.svg|700]] %%[[Excalidraw-Solution/双指针_2.excalidraw.md|🖋 Edit in Excalidraw]]%% --- # 双指针——主次指针（辅助指针）通常**外层采用 `for` 循环**的写法，是对**主指针 `j`** 的移动，循环内**视==情况/条件==移动左指针**。 - **主指针 `j`** 指向**剩余==待搜索区间的头部==**，即**当前待判断元素**。 - **次指针/==辅助指针==** `i` 指向已得到**序列==尾部的后一位==**，即 **==待插入下一个有效元素==** 的位置，`i` 的值即为当前有效元素长度。 - `j` 每次移动一步，逐个扫描元素，若 `i` 和 `j` 满足条件，则并后移 `i`：`++i` 。 ```cpp int n = seq.size(); // 循环不变量: j指向剩余待搜索区间的头部, i指向已处理区间尾部的"后一位". int i = 0; for (int j = 0; j < n && i < m; ++j) { if (satisfy(seq, i, j)) { // do something... process_pos(seq, i, j); ++i; // 移动辅助指针 } } ``` ### 扩展：荷兰国旗算法——三指针（一个主指针，两个辅助指针） - **主指针 `i`** 指向**剩余==待搜索区间的头部==**，即**当前待判断元素**。 - **两个辅助指针`j`、`k`** 分别**指向==两段序列==各自的==尾部的后一位==**，即 **==待插入下一个有效元素==** 的位置。 ###### 示例一：荷兰国旗问题（Dutch National Flag Algorithm）将只含有 **0、1、2 三值**的数组**重排列**，使得相同值的元素相邻，同时整体分成 0、1、2 三段） ###### 示例二：将区间`[l, r]`内元素依次分成 `<val`、`==val`、`>val` 的三段 **循环不变量**： - 主指针 `i` 指向 **==剩余待处理区间==的头部**，即**当前待处理元素**； - 指针 `lt` 指向 `<val` 的**序列尾部的后一位**，即 "**==待插入==下一个 `<val` 的元素的位置**"； - 指针 `gt` 指向 `>val` 的**序列头部的前一位**，即 "**==待插入==下一个 `>val` 的元素的位置**"。 - 区间划分： - `[l, lt)` 为 `< val` 的序列； - `[lt, gt]` 为 `==val` 的序列； - `(gt, r]` 为 `> val` 的序列； - `[i, gt]` 为 "**剩余待处理区间**"，因此循环条件为 `i <= gt`，即 **==剩余待搜索区间非空==** ```cpp // 将区间arr[l, r]内的元素划分成`<pivot`, `==pivot`, `>pivot`三段. void Partition(vector<int> &arr, int l, int r, int pivot) { int lt = l; int gt = r; int i = l; while (i <= gt) { // 区间[i, gt]为剩余待搜索区间. 循环条件即为该区间非空. if (arr[i] < pivot) { // 由于[lt, i)区间全为==val的元素, 所以交换到位置i的就是val值. // 因此同时后移 lt 和 i. swap(arr[i++], arr[lt++]); } else if (arr[i] > pivot) { swap(arr[i], arr[gt--]); } else { // arr[i] == pivot ++i; } } } ``` # 双指针——位置处理双指针 `i` 和 `j` 每次用于 **==提取==**/处理 **==两个位置==**。即**两个指针至少有一方的位置是不确定**的，每次都需要**先移动两个指针直至指向目标位置**，从而**提取两个元素进行处理**。通常有两种等价的写法：**单层 for 循环**、**双层 while 循环**； ## 双指针指向同一序列 #### 单层 for 循环的写法 ```cpp int j = 0; // 逐位检查左边界, 为每一个有效左边界，找到满足条件的最大右边界. // 与下面的双层while循环本质上相同. for (int i = 0; i < n; ++i) { if (satisfy_pos(seq, i)) { // 可作为左边界 j = min(i + 1, j); while (j < n && !satisfy_pos(seq, j)) ++j; // 找到满足条件的右边界. if (j == n) break; // 处理位置i和j process_pos(seq, i, j); ++j; } } ``` #### 双层 while 循环的写法 > while 双层循环的写法，双指针 `i` 和 `j` 都指向当前**待处理位置**，外层循环的逻辑是 "每次**处理两个指针所指的一对位置 `i`, `j`**" ##### 同向移动 ```cpp int n = seq.size(); // 循环不变量: i指向"i对应的剩余待处理区间的头部", j指向"j对应的剩余待处理区间的头部" int i = 0, j = 0; while (j < n) { // 或者 `i <= j`, 取决于具体场景 // 外层循环的逻辑: 每次尝试令指针i和j指向两个"有效位置", 取两指针所指元素进行处理. // 1. 移动i直到下一个有效位置 while (i < n && !satisfy(seq, i)) ++i; // 2. 保证j在i右侧, 并且移动j直到指向下一个有效位置 j = max(i + 1, j); // 如果允许i和j重合, 则这里取`j = max(i, j);`. while (j < n && !satisfy(seq, j)) ++j; // 处理位置i和j if (i < n && j < n) { process_pos(seq, i, j); } // 当前位置已处理完, 后移i和j, 使其分别指向下一个待处理位置. ++i; ++j; } ``` ##### 首尾相向移动 ```cpp int n = seq1.size(); // 循环不变量: i、j分别"剩余待处理区间的头部、尾部" int i = 0, j = n - 1; while (i < j) { // 或者 `i <= j`, 取决于具体场景 // 外层循环的逻辑: 每次尝试令指针i和j指向两个"有效位置", 取两指针所指元素进行处理. // 1. 确定左、右指针指向有效位置, 或越界 while (i < j && ...) ++i; // 如果每次固定移动1位, 则省略while循环 while (i < j && ...) --j; // 如果每次固定移动1位, 则省略while循环 // 处理位置i和j. if (i < j) process_pos(i, j); // 当前位置i和j已完成处理, 后移i和j, 使其指向"待搜索区间", 保证循环不变量成立 ++i; --j; } // 退出循环时, i >= j. ``` ## 双指针指向两个序列 > while 双层循环的写法，双指针 `i` 和 `j` 都指向当前**待处理位置**，外层循环的逻辑是 "每次**处理两个指针所指的一对位置 `i`, `j`**" ```cpp title:two_pointers_to_two_sequence.cpp int n = seq1.size(), m = seq2.size(); // 循环不变量: i、j均指向"剩余待处理区间的首个元素" int i = 0, j = 0; while (i < n || j < m) { // 或者`i < n && j < m`, 或者单一条件`j < m`等, 取决于具体场景 // 外层循环的逻辑: 每次尝试令指针i和j指向两个"有效位置", 取两指针所指元素进行处理. // 1. 确定左指针指向有效位置, 或越界 while (i < n && ...) ++i; // 如果是每次固定移动一位, 则省略此处while循环 // 2. 确定右指针指向有效位置, 或越界 while (j < m && ...) ++j; // 如果是每次固定移动一位, 则省略此处while循环 // 处理位置i和j. if (i < n && j < m) { // 两指针位置有效 // ... process_pos(i, j); } else if (i < n || j < m) { // 仅其中一个指针位置有效, 另一指针越界 // ... } // 当前位置i和j已完成处理, 后移i和j, 使其指向"待搜索区间", 保证循环不变量成立 ++i; ++j; } // 退出循环时, 两个指针均越界. // do something... ``` # 双指针——区间确认/区间提取通过**两个指针**来标记区间的**左**、**右边界**，每次确定一个「 **==最大化的、边界不可再扩张的目标区间段==** 」后对该区间段进行处理，随后再去 **==剩余待搜索区域==** 中**找下一个目标区间段**。双指针用于在 **一般序列 / 单调性序列** 上提取/确认区间时，**写法不同**： - 对于 "**==一般序列==**"：目的在于 "**==提取==** 一个极大目标区间" 进行处理； - 通常包括两种写法： 1. 方式一：**单层 `for` 循环**写法 2. 方式二：**双层 `while` 循环**写法 - 对于 "**==单调性序列==**"：目的在于 **==枚举==** 每个位置作为**左边界或右边界**，扩展/收缩得到对应的"极大右边界/极小左边界"，取得**极大/极小的目标区间**。 - 写法通常为 "**外层 `for` 循环** + **内层 `while` 循环**" ： - 外层 `for` 循环 **==枚举==各个位置**作为**左边界或右边界**； - 内层 `while` 循环用于==**扩展==极大右边界** 或 **==收缩==左边界**；无论采用哪种写法，都推荐以 "**左开右闭区间 `[l, r)` 表示当前极大区间**" 作为 **==循环不变量==**，令 `r` 始终指向 "**剩余待搜索区间的头部**"。 ## （1）"一般序列"上提取区间有两种等价的常见写法：1）单层 `for` 循环写法； 2）双层 `while` 循环的写法； #### 单层 for 循环写法：逐位遍历 > 逻辑：逐位遍历各个位置，检查是否可作为**左边界**，或者**右边界**。 1. **方式一**：适用于**必须**要得到一段 "**==最大化、不可再扩张的完整区间==**" 后才能进行 **==记录、处理==** 的情况，例如**获取一段完整目标字符串**后才进行哈希映射。 1. 若当前位置满足条件，则右边界后移； 2. 若当前位置不满足条件（包括 **==越界==** 时），则"**记录/处理前一段区间**"， 然后**重置左边界**为当前位置； 3. 需要在循环外 **==单独处理最后一个区间==**。 2. **方式二**：每次得到一个**合法区间**（不一样是最大化的，或许仍能继续扩张）就进行**记录** 1. 若当前位置满足条件, 则"**记录当前区间长度**"，**右边界后移**； 2. 若当前位置不满足条件, 则**重置左边界**为当前位置； > [!caution] > - 如果是在**不合法位置**才处理，就要在**循环外单独处理越界**的情况。 > - 如果是在**满足条件的合法位置边界处**进行处理，在处理完合法位置（例如添加答案等）的最后，就需要移动指针，指向剩余待处理位置。 ##### 标准模版写法一：**只在 "==当前位置满足条件==" 时进行处理，并==检查后一位==是否无效；** ❇️（推荐） ```cpp // 写法一：只对满足条件的位置进行处理, 并且检查后一位是否无效. int l = -1; for (int r = 0; r < n; ++r) { if (satisfy(r)) { // 1.纳入当前位置, 更新区间状态. include(r); update(state); // 2.检查是否可作为左边界 if (l == -1) l = r; // 3.检查是否为右边界 if (r == n - 1 || !satisfy(r + 1)) { process_sec(seq, l, r); // 获取一段极大区间[l, r] // 重置区间状态, 重置左边界. reset(state); l = -1; } } } ``` 写法二：对每个位置分两个逻辑：**满足条件时如何处理，不满足条件时如何处理** ```cpp // 写法二: 不满足条件时, 若得到一段极大区间, 则进行处理; int l = -1; for (int r = 0; r < n; ++r) { if (satisfy(r)) { // 1.检查是否作为左边界 if (l == -1) l = r; // 2.纳入当前位置, 更新区间状态. include(r); update(state); } } else { // !satisfy(r) if (l != -1) { // 得到一段极大区间[l, r] process_seq(seq, l, r); reset(state); l = -1; } } } // 需要处理最后一段极大区间[l, n-1] if (l < n) process_sec(seq, l, n-1); ``` ##### 简化模版 ```cpp int n = seq.size(); // 循环不变量: [l, r) 表示当前待处理区间. r指向剩余待搜索区间头部. int l = 0; for (int r = 0; r < n; ++r) { // 省略了`satisfy(seq, r)`成立的处理逻辑 if (r == n - 1 || !satisfy(seq, r + 1)) { // 得到一段"最大化" process_sec(seq, l, r); l = r + 1; // 更新l指向当前r的后一位置. } } // 如果for循环中没有处理`r` == n-1时的情况, 则这里必须如下做额外处理. // if (l < n) process(l, n - 1); ``` #### while 双层循环写法：每次获取一段完整区间 ❇️ > 本质：外层循环逻辑为 "**每次==确认/提==取一段完整的目标区间 `[l, r)`（极大右边界，不可再扩展）并进行处理**"。 - **外层循环每轮完成：==找到/确定一个目标区间== & ==处理该区间==**，步骤为： 1. 确定**区间==左边界==** 2. 确定**区间==右边界==** 3. 处理**区间** - **内层循环用于上述步骤中，确定"区间==左、右边界=="**； ```cpp int l = 0, r = 0; // 循环不变量: [l, r)表示当前有效区间, r指向剩余待搜索区间的头部. // 外层循环每次确认/提取一段完整的目标区间 `[l, r)`（极大右边界，不可再扩展）并进行处理 while (r < n) { // 1.确定左边界: 跳过不满足的位置, 直到首个满足条件的位置. while (r < n && !satisfy(seq, r)) ++r; if（r == n） break; // 不存在有效区间 l = r; // 明确左边界存在. // 2.确定右边界: 跳过满足条件的位置, 直至首个不满足条件的位置. ++r; // 如果要保证 r 始终在l右侧, 则这里需要先后移一步. 如果r和l可重叠, 允许区间[l, r)长度为0, 则省略此行. while (r < n && staisfy(seq, r)) { // do something... ++r; } // 3. 得到有效区间[l, r) 上面已判断左边界存在, 因此区间长度至少为1. process_sec(seq, l, r-1); } // 其实 l 可以直接放在循环内定义, 每次确定起点后才需要l int r = 0; while (r < n) { while (r < n && !satisfy(seq, r)) ++r; if (r == n) break; int l = r; // 确定起点 // ... 其余同上 } ``` ##### 示例 ###### 找出所有连续相同内容的区间 ```cpp // 循环不变量: r指向剩余待处理区间的头部 // [l, r)为上一个已处理区间. l初始值是多少都无所谓. int l = 0, r = 0; while (r < n) { // j指向剩余待处理区间 // 确定左边界, 找出连续相同字符的最大区间[l, r) l = r; while (r < n && nums[r] == nums[l]) { // do something. ++r; } // 处理区间[l, r) process(l, r - 1); } ``` ## （2）"==单调性==序列"上搜索区间 > 目的在于寻找合法的 "最大**左右边界**"，要求序列本身**具有==单调性==**，**保证两个指针移动后都==不需要回头==**。 ### 枚举左边界，扩展最大右边界 > 本质：**枚举以每一个位置 `l` 作为==左边界==的情况**，在满足条件或不满足条件为其 **==扩展==得到最大右边界 `r`**，构成**有效区间 `[l, r)`** ```cpp int n = seq.size(); // 循环不变量: [l, r) 表示当前区间. r指向剩余待搜索区间的头部. int r = 0; // 枚举以每一个位置 `l` 为左边界的情况, 每次移动一步左边界l. // 为每个seq[l]找到极大有效区间[l, r). for (int l = 0; l < n; ++l) { // 对每个seq[l], 扩展得到相应的最大右边界r, 构成区间[l, r). r = max(l + 1, r); // 保证j在i右侧. 若l,r可重叠, 即允许区间[l,r)长度为0, 则取 `r = max(l, r);` // 若去掉上一行, 则下面循环应当为`while (r <= l || r < n && satisfy(seq, r))` while (r < n && satisfy(seq, r)) ++r; // 得到i对应的最大有效区间[l, r) process_sec(l, r-1); } ``` > 扩展情况：为每个位置 `i` 的 `seq[i]` 找到的有效区间 `[l, r)`； ```cpp // 扩展情况: // 为每个seq[i]找到的有效区间[l, r). int l = 0, r = 0; for (int i = 0; i < n; ++i) { // 对每个seq[i]: // 1. 不满足条件时扩展右边界j, 得到有效区间的起始左边界k. r = max(l + 1, r); // 保证j在i右侧. 若l,r可重叠, 即允许区间[l,r)长度为0, 则取 `r = max(l, r);` // 若去掉上一行, 则下面循环应当为`while (r <= l || r < n && satisfy(seq, r))` while (r < n && !satisfy(seq, r)) ++r; if (r == n) break; // 不存在有效区间. // 2. 满足条件时继续扩展右边界, 得到有效区间的最大右边界r-1. l = r; // k是有效区间的起始左边界. while (r < n && satisfy(seq, r)) ++r; // 得到i对应的最大有效区间[l, j). 上面已经判断r未越界, 因此这里区间大小至少为1. process_sec(seq, l, r-1); } ``` ### 枚举右边界，收缩左边界（变长 ==滑动窗口== ） > 本质：**枚举以每一个位置 `j` 作为==右边界==的情况**，在满足条件或不满足条件时 **==收缩==得到最右左边界 `i`**，构成**有效区间 `[i, j) ```cpp int n = seq.size(); // 循环不变量: [l, r) 表示当前区间. r指向剩余待搜索区间的头部. int l = 0; // 枚举以每一个位置`r`作为右边界的情况, 每次移动一步右边界r. for (int r = 0; r < n; ++r) { // 右边界右移一位, 纳入新位置seq[r]. include(seq, r); // 检查是否需要收缩左边界 while (l <= r && check_seq(seq, l, r)) { // 满足条件时收缩, 或者不满足条件时收缩 // 处理当前窗口 process_sec(seq, l, r); // 如果收缩条件是"窗口即为所需窗口时收缩", 则每次收缩前都要先记录当前窗口状态. // 收缩左边界. exclude(seq, l); ++l; } // 以当前j为右边界的"最小窗口"[i, j]. process_sec(seq, l, r); // 如果收缩条件是"窗口非所需窗口时收缩", 则最终收缩为目标窗口后, 再记录窗口状态 } ``` # 双指针——区间扩展 ![[00-数据结构与算法笔记/循环不变量#（3）从某一位置起扩展得到满足条件的最大区间|循环不变量]] # 参考资料 # Footnotes