模式二指针

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

概述

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

我已解决的问题列表

简单的

中等的

难的