双指针技巧深度解析：从基础到巅峰（Java 最优解）

大家好！如果你是算法爱好者、LeetCode刷题党，或者准备大厂面试，那双指针（Two Pointers）技巧绝对是你的“杀手锏”。它能把O(n²)暴力解优化到O(n)，在数组、链表、字符串问题中大放异彩。本文从基础概念入手，逐步深入到高级应用，全用Java代码展示最优解。结合图示和LeetCode经典题，带你从“会用”到“巅峰掌握”。无论新手还是老鸟，都能收获满满！

1. 双指针技巧简介

1.1 什么是双指针？

双指针是一种算法设计技巧，使用两个指针（通常是索引或引用）在数据结构（如数组、链表）上移动，高效解决问题。核心思想：通过指针的相对移动，减少遍历次数，避免嵌套循环。

• 为什么用双指针？
  暴力法往往是双层循环，时间O(n²)；双指针能线性扫描，时间O(n)，空间O(1)。
• 适用场景：
• 已排序数组的查找（Two Sum）
• 链表操作（检测环、反转）
• 滑动窗口（子串、子数组）
• 去重、partition

1.2 双指针的优势与缺点

优势：高效、简单、直观。
缺点：需要数据有序或特定结构；边界条件易错（null、空数组）。

以下是双指针在数组上的典型示意图，帮助直观理解指针移动：

图中left和right从两端向中间移动，常用于求和或配对问题。

2. 双指针的类型分类

双指针主要有三种变体，根据移动方向和速度分类：

类型	描述	典型应用	时间复杂度
左右指针（Opposite Directions）	一个从头（left=0），一个从尾（right=n-1），向中间移动	Two Sum、反转数组、雨水收集	O(n)
快慢指针（Fast & Slow）	slow从头慢移，fast从头快移（通常fast走2步，slow走1步）	检测链表环、中间节点、删除倒数第N节点	O(n)
同向指针（Sliding Window）	left和right同向移动，right扩展窗口，left收缩	最长子串、子数组和	O(n)

2.1 左右指针示例

如图，在排序数组中求Two Sum：如果sum > target，right左移；sum < target，left右移。

2.2 快慢指针示例

如图，检测链表环：fast追上slow即有环。

2.3 同向指针示例

类似窗口：right前进扩展，left前进收缩，维护窗口内条件。

3. 基础应用：LeetCode经典题（Java最优解）

我们从简单题入手，逐步代码实战。所有代码都是O(n)最优，注释详尽。

3.1 左右指针：Two Sum II (LeetCode 167)

问题：给定排序数组，找两个数和为target，返回索引（1-based）。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};  // 1-based
            } else if (sum < target) {
                left++;  // 需更大，左移
            } else {
                right--;  // 需更小，右移
            }
        }
        return new int[]{-1, -1};  // 无解
    }
}

时间O(n)，空间O(1)。边界：left < right防止交叉。

3.2 快慢指针：Remove Duplicates from Sorted Array (LeetCode 26)

问题：原地删除排序数组重复项，返回新长度。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int slow = 0;  // 指向唯一元素位置
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];  // 覆盖重复
            }
        }
        return slow + 1;  // 新长度
    }
}

fast扫描，slow放置唯一值。变体：允许重复k次（LeetCode 80）。

3.3 快慢指针：Linked List Cycle (LeetCode 141)

问题：判断链表是否有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;  // fast领先一步
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;         // 慢1步
            fast = fast.next.next;    // 快2步
        }
        return true;  // 相遇即有环
    }
}

Floyd判圈算法。进阶：找环入口（LeetCode 142）。

4. 高级应用：从滑动窗口到复杂变体

4.1 滑动窗口：Longest Substring Without Repeating Characters (LeetCode 3)

使用左右指针维护无重复窗口。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] lastSeen = new int[128];  // ASCII最后出现位置
        Arrays.fill(lastSeen, -1);
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen[c] >= left) {  // 重复，移动left
                left = lastSeen[c] + 1;
            }
            lastSeen[c] = right;
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

时间O(n)，优化HashMap为数组。

4.2 雨水收集（Trapping Rain Water, LeetCode 42）

左右指针计算每个位置能接的水。

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                water += leftMax - height[left++];
            } else {
                rightMax = Math.max(rightMax, height[right]);
                water += rightMax - height[right--];
            }
        }
        return water;
    }
}

O(n)时间，O(1)空间。维护左右最大高度。

4.3 巅峰变体：3Sum (LeetCode 15)

三指针：固定一个，剩余用双指针求Two Sum。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  // 先排序
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // 去重
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;  // 去重
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++; right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

处理去重是关键。

5. 常见问题与优化技巧

• 边界处理：空数组、单元素、所有相同元素。
• 去重：排序后跳过相同值。
• 时间优化：确保指针单向移动，避免回溯。
• 空间优化：原地修改数组。
• 面试Tips：画图解释过程（如快慢指针追击）；讨论变体（如k Sum）。

常见LeetCode题单：11（Container With Most Water）、125（Valid Palindrome）、283（Move Zeroes）、344（Reverse String）、876（Middle of Linked List）。

6. 总结与实践建议

双指针是算法“从基础到巅峰”的桥梁：基础是理解移动规则，巅峰是灵活变体（如多指针、窗口）。在Java中，优先用数组/链表实现，注意类型安全。

实践建议：

• LeetCode专题刷题：Two Pointers标签。
• 手绘过程：用纸笔模拟指针移动。
• 扩展：结合二分、哈希，解决更复杂问题。

希望这篇文章让你对双指针了如指掌！有具体题不会，欢迎评论。继续刷题，巅峰见！🚀