模式二指针

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《模式二指针》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

• 概述
  • 何时使用两指针模式
  • 两个指针的关键概念
  • 常见的两指针问题类别
  • 两个指针的优点
  • 常见挑战和技巧
• 可视化
• 可视化示例
• 我已解决的问题列表
  • 简单
  • 中
  • 难

概述

两指针模式是一种常见的算法技术，用于有效解决各种问题，特别是涉及数组或字符串的问题。通过策略性地在输入中放置和移动两个指针（或索引），您可以减少对嵌套循环的需求，通常可以将时间复杂度从 o(n^2) 提高到 o(n) 或 o(nlogn)。

何时使用两指针模式

1. 排序数组：

   • 当输入数组排序时，两个指针可以帮助有效地找到满足特定条件（例如，总和、差值或目标值）的元素。

2. 搜索对/三胞胎：

   • 查找满足特定总和或条件的对或三元组。

3. 分区问题：

   • 根据条件重新排列数组（例如，分隔 0 和 1，或荷兰国旗问题）。

4. 优化问题：

   • 最大化或最小化结果，例如装水的最大容器。

5. 回文问题：

   • 验证或构造回文字符串。

两个指针的关键概念

1. 两个指针相互靠近：

   • 一个指针从开头开始，另一个指针从结尾开始。
   • 常见问题如下：
     • 验证回文。
     • 装最多水的容器。
     • 两和（排序输入）。

2. 两个指针朝同一方向移动：

   • 两个指针都从左向右移动，但速度不同或在特定条件下移动。
   • 常见问题如下：
     • 从排序数组中删除重复项。
     • 找到最小大小的子数组总和。

3. 固定指针 移动指针：

   • 一个指针固定，另一个探索数组。
   • 常见于三元组问题（如 3sum）或分区问题（如排序颜色）。

常见的两指针问题类别

1. 两指针搜索：

   • 诸如在排序数组中查找总和为目标值的两个数字之类的问题。

2. 分区和重新排列：

   • 单次排序 0、1 和 2 等问题。

3. 回文检查和字符串操作：

   • 验证字符串是否为回文等问题。

4. 最大化/最小化结果：

   • 诸如截留雨水或最大化“水最多的容器”问题中的面积等问题。

两个指针的优点

• 高效：

  • 通常会显着降低时间复杂度。
  • 与排序结合使用时，通常在 (o(n)) 或 (o(n log n)) 中进行操作。

• 直观：

  • 为涉及对、三元组或范围的问题提供简单的逻辑结构。

• 空间效率：

  • 就地工作，通常需要 (o(1)) 额外空间。

常见挑战和技巧

1. 排序输入：

   • 如果输入未排序但排序有帮助，请考虑使用 (o(nlogn) 排序进行预处理。

2. 边缘情况：

   • 处理空输入、单个元素或重叠范围的情况。

3. 了解条件：

   • 根据问题约束明确定义何时以及如何移动指针。

可视化

• 以上理论很好，更容易阅读，但很难实现。
• 如果您想更好地掌握这种模式，您需要可视化这两个点的移动和行为方式（这说起来容易做起来难）。
• 在迭代数组时，使用以下辅助方法可视化数组以及两个指针。
• 从 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 array
private 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 string
private 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 

我已解决的问题列表

简单的

中等的

难的

本篇关于《模式二指针》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！