概述何时使用两指针模式两个指针的关键概念常见的两指针问题类别两个指针的优点常见挑战和技巧可视化可视化示例我已解决的问题列表简单中难
概述
两指针模式是一种常见的算法技术，用于有效解决各种问题，特别是涉及数组或字符串的问题。通过策略性地在输入中放置和移动两个指针（或索引），您可以减少对嵌套循环的需求，通常可以将时间复杂度从 o(n^2) 提高到 o(n) 或 o(nlogn)。
何时使用两指针模式
排序数组：
当输入数组排序时，两个指针可以帮助有效地找到满足特定条件（例如，总和、差值或目标值）的元素。
搜索对/三胞胎：
查找满足特定总和或条件的对或三元组。
分区问题：
根据条件重新排列数组（例如，分隔 0 和 1，或荷兰国旗问题）。
优化问题：
最大化或最小化结果，例如装水的最大容器。
回文问题：
验证或构造回文字符串。
两个指针的关键概念
两个指针相互靠近：
一个指针从开头开始，另一个指针从结尾开始。常见问题如下：验证回文。装最多水的容器。两和（排序输入）。
两个指针朝同一方向移动：
两个指针都从左向右移动，但速度不同或在特定条件下移动。常见问题如下：从排序数组中删除重复项。找到最小大小的子数组总和。
固定指针 移动指针：
一个指针固定，另一个探索数组。常见于三元组问题（如 3sum）或分区问题（如排序颜色）。
常见的两指针问题类别
两指针搜索：
诸如在排序数组中查找总和为目标值的两个数字之类的问题。
分区和重新排列：
单次排序 0、1 和 2 等问题。
回文检查和字符串操作：
宣小二
宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。
21 查看详情 验证字符串是否为回文等问题。
最大化/最小化结果：
诸如截留雨水或最大化“水最多的容器”问题中的面积等问题。
两个指针的优点
高效：
通常会显着降低时间复杂度。与排序结合使用时，通常在 (o(n)) 或 (o(n log n)) 中进行操作。
直观：
为涉及对、三元组或范围的问题提供简单的逻辑结构。
空间效率：
就地工作，通常需要 (o(1)) 额外空间。
常见挑战和技巧
排序输入：
如果输入未排序但排序有帮助，请考虑使用 (o(nlogn) 排序进行预处理。
边缘情况：
处理空输入、单个元素或重叠范围的情况。
了解条件：
根据问题约束明确定义何时以及如何移动指针。
可视化
以上理论很好，更容易阅读，但很难实现。 如果您想更好地掌握这种模式，您需要可视化这两个点的移动和行为方式（这说起来容易做起来难）。在迭代数组时，使用以下辅助方法可视化数组以及两个指针。 从 for 循环内部调用辅助方法。使用前缀参数分隔算法中的两条不同的行
左指针表示为()，右指针表示为[]。如果两个指针指向相同的索引，则表示为[()]。
int[] : 整数数组
private void tpi(int[] s, int l, int r, string... prefix) { if (prefix.length == 0) { prefix = new string[] { "" }; } system.out.print(prefix[0]); for (int i = 0; i < s.length; i++) { if (i == l && i == r) { system.out.printf("[(%s)]", s[i]); } else if (i == l) { system.out.printf("(%s)", s[i]); } else if (i == r) { system.out.printf("[%s]", s[i]); } else { system.out.print(s[i]); } system.out.print(" "); } system.out.println();}
char[]：字符数组
// two pointer char arrayprivate void tpc(char[] s, int l, int r, string... prefix) { if (prefix.length == 0) { prefix = new string[] { "" }; } system.out.print(prefix[0]); for (int i = 0; i < s.length; i++) { if (i == l && i == r) { system.out.printf("[(%s)]", s[i]); } else if (i == l) { system.out.printf("(%s)", s[i]); } else if (i == r) { system.out.printf("[%s]", s[i]); } else { system.out.print(s[i]); } system.out.print(" "); } system.out.println();}
字符串：字符串
// two pointer stringprivate void tps(string s, int l, int r, string... prefix) { if (prefix.length == 0) { prefix = new string[] { "" }; } system.out.print(prefix[0]); for (int i = 0; i < s.length(); i++) { if (i == l && i == r) { system.out.printf("[(%s)]", s.charat(i)); } else if (i == l) { system.out.printf("(%s)", s.charat(i)); } else if (i == r) { system.out.printf("[%s]", s.charat(i)); } else { system.out.print(s.charat(i)); } system.out.print(" "); } system.out.println();}
可视化示例
例如 leetcode 问题：283. 移动零
解决方案
class solution { private void tpi(int[] s, int l, int r, string... prefix) { if (prefix.length == 0) { prefix = new string[] { "" }; } system.out.print(prefix[0]); for (int i = 0; i < s.length; i++) { if (i == l && i == r) { system.out.printf("[(%s)]", s[i]); } else if (i == l) { system.out.printf("(%s)", s[i]); } else if (i == r) { system.out.printf("[%s]", s[i]); } else { system.out.print(s[i]); } system.out.print(" "); } system.out.println(); } public void movezeroes(int[] nums) { int l = 0, r = 0; while (r < nums.length) { tpi(nums, l, r); if (nums[r] != 0) { nums[l] = nums[r]; l++; tpi(nums, l, r, "replaced: "); } r++; } while (l < nums.length) { nums[l++] = 0; tpi(nums, l, r, "remaining: "); } }}
输入：nums = [0,1,0,3,12]
标准输出
[(0)] 1 0 3 12 (0) [1] 0 3 12 Replaced: 1 [(1)] 0 3 12 1 (1) [0] 3 12 1 (1) 0 [3] 12 Replaced: 1 3 (0) [3] 12 1 3 (0) 3 [12] Replaced: 1 3 12 (3) [12] Remaining: 1 3 12 0 (12) Remaining: 1 3 12 0 0
我已解决的问题列表
简单的
125. valid palindrome13-12-2024283. move zeroes13-12-2024344. reverse string13-12-2024
中等的
3. longest substring without repeating characters13-12-202411. container with most water13-12-202415. 3sum13-12-202475. sort colors13-12-2024167. two sum ii – input array is sorted13-12-2024209. minimum size subarray sum13-12-2024
难的
42. trapping rain water13-12-2024
以上就是模式二指针的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/614216.html
微信扫一扫 
支付宝扫一扫 
