01. 双指针-只有一个输入, 从两端开始遍历

正文

双指针（Two Pointers）是一种常用于数组或字符串问题的技巧。当我们需要在有序序列中查找符合特定条件的元素对，或者判断序列是否具有某种属性（如回文）时，从两端向中间遍历是非常高效的。

算法模板

fun doublePointer(arr: IntArray): Int {
    var left = 0
    var right = arr.size - 1

    while (left < right) {
        // 根据 left 和 right 相关的条件进行操作
        // 例如：if (arr[left] + arr[right] == target) return ...
        
        if (CONDITION) {
            left++
        } else {
            right--
        }
    }

    return 0 // 返回需要的结果
}

使用说明

1. 适用场景：

   • 有序数组：如两数之和（有序版）、三数之和。
   • 字符串处理：如判断回文字符串、反转数组/字符串。
   • 容器盛水问题：如“盛最多水的容器”。

2. 核心优势：

   • 能够将 $O(N^2)$ 的暴力枚举优化到 $O(N)$。
   • 利用了序列的有序性或特定单调性。

3. 注意点：

   • 循环条件通常是 left < right（找对子）或 left <= right（处理中间元素）。
   • 更新指针时要确保逻辑能够覆盖所有情况，避免死循环。