Interview

Two Pointer Technique

Two-pointer technique explained with classic code challenges and Java solutions — inward traversal, unidirectional traversal, and staged traversal patterns.

双指针算法

介绍

双指针是一种用两个索引变量代替一个索引遍历数据结构的算法模式。它能让我们在一次遍历中完成比较和操作，常将 O(n²) 的暴力解法优化到 O(n)。

一句话直觉：两个指针 = 一个循环干两件事。一个指针探索，一个指针记录；或两个指针从两端收缩。

双指针的两个适用条件：

数据有可预测的变化规律 — 最常见的就是有序数组，移动指针时能预知相邻元素的大小关系
需要找一对值，或答案可以由两个值生成

双指针通常要求线性数据结构，比如数组或链表。

三种模式

1. 相向遍历 (Inward Traversal)

两个指针分别从两端出发，向中间靠拢。适用于需要比较数据结构两端元素的场景。

适用问题：有序数组的两数之和、三数之和、回文判断、最大容器

2. 同向遍历 (Unidirectional Traversal)

两个指针从同一端出发，同向移动。通常右指针负责”探索”，左指针负责”记录”。

适用问题：移动零到末尾、移除重复元素、滑动窗口

3. 分段遍历 (Staged Traversal)

第一个指针先找到某个条件，第二个指针基于第一个指针的位置继续查找额外信息。

适用问题：下一个字典序排列

代码挑战

1. Two Sum II

问题：给定一个已按升序排列的整数数组，找出两个数使它们的和等于目标值，返回两个数的索引（1-based）。

双指针思路：左指针从 0 出发，右指针从末尾出发。和太小 → 左指针右移；和太大 → 右指针左移。O(n) 时间，O(1) 空间。

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

延伸问题

Q: 如果数组没有排序，双指针还能用吗？ 可以先排序再双指针 — O(n log n) 时间，O(1) 空间。也可以用 HashMap 一次遍历 — O(n) 时间，O(n) 空间。如果只需要返回 true/false（不需要索引），排序 + 双指针更省空间。
Q: 如果需要找出所有不重复的两数组合（不止一对），该怎么改？ 找到一对后不直接返回，而是同时移动左右指针并跳过重复值（类似 3Sum 的去重逻辑），将所有符合条件的组合收集到结果列表中。

2. Container With Most Water

问题：给定一个非负整数数组表示挡板高度，找出两个挡板之间能容纳的最大水量。

双指针思路：左右指针从两端出发。容积 = min(height[left], height[right]) × (right - left)。每次移动较矮的挡板 — 因为移动较高的那边只会让容积变小。O(n) 时间。

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        int h = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, h * (right - left));

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

延伸问题

Q: 为什么移动较矮的挡板一定是对的？能否严格证明？ 面积由两个因素决定：宽度（right - left）和高度（min(height[left], height[right])）。宽度在每一步缩小 1，是不可避免的。高度受限于较短挡板 — 如果移动较高的挡板，新高度的上限仍然是原来的较短挡板（甚至更低），面积只减不增。只有移动较短挡板，才有可能遇到更高的挡板来弥补宽度损失。因此移动较短挡板是唯一可能增大面积的选择。
Q: 这道题和 Trapping Rain Water（接雨水）有什么区别？ Container 找的是两个挡板之间的最大矩形面积（只有一个”桶”）；Trapping Rain Water 计算的是所有位置上方能积累的雨水总和（多个”坑”叠加）。Container 用贪心双指针，Rain Water 需要额外记录左右最大高度或用单调栈。

3. Valid Palindrome

问题：判断一个字符串是否为回文，只考虑字母和数字，忽略大小写。

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

        if (Character.toLowerCase(s.charAt(left))
                != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

延伸问题

Q: 如果可以删除最多一个字符，怎么判断？（Valid Palindrome II） 同样用双指针，当首次遇到不匹配时，分别尝试跳过左字符或右字符，检查剩余的 substring 是否为回文。两个分支中只要有一个成立即可返回 true。时间复杂度 O(n)。
Q: 如何用双指针判断一个单链表是否为回文？ 用快慢指针找到链表中点（快指针每次走两步，慢指针走一步），反转后半部分链表，然后从头和从中点同时遍历比较。这也是双指针的一种应用 — 一个找中点，一个做比较。

关键技巧

排序是双指针最好的朋友 — 排序后数据有可预测的变化规律
去重 — 使用 while (left < right && nums[left] == nums[left+1]) 跳过重复值
倒序填充 — 当需要从大到小排列时，从数组尾部开始填可以避免额外空间
移动较短的一边 — 在 Container 类问题中，移动较矮的挡板是贪心的关键

参考资料

附加练习

Problems that extend the patterns above — kept as references to keep the main section focused on core inward traversal.

3Sum — Two Sum II 延伸：固定一个数 + 双指针，O(n²)
Move Zeroes — 同向双指针，原地操作
Squares of a Sorted Array — 双指针 + 倒序填充