双指针技巧在数组与链表问题中的应用 一、问题描述 双指针技巧是一种通过维护两个指针（索引）在数据结构中按特定规则移动来高效解决问题的方法。它常用于数组或链表问题，通过减少循环嵌套或避免重复计算来优化时间复杂度。典型场景包括： 有序数组的两数之和 （指针从两端向中间移动）。 判断链表是否有环 （快慢指针检测循环）。 合并两个有序数组 （指针从后向前填充避免覆盖）。 二、解题原理与步骤 双指针的核心思想是通过指针的移动规律将时间复杂度从O(n²)优化到O(n)。以下是三种常见类型的详细分析： 1. 左右指针（对撞指针） 适用场景 ：有序数组的区间操作或搜索问题。 示例问题 ：在升序数组中找到两个数，使它们的和等于目标值。 步骤 ： 初始化左指针 left=0 ，右指针 right=n-1 。 循环条件： while left < right 。 计算当前和 sum = nums[left] + nums[right] ： 若 sum == target ，返回结果。 若 sum < target ，说明需要更大的数，左指针右移（ left++ ）。 若 sum > target ，说明需要更小的数，右指针左移（ right-- ）。 时间复杂度从暴力法的O(n²)降至O(n)。 2. 快慢指针 适用场景 ：链表循环检测、寻找中点或倒数第k个节点。 示例问题 ：判断单链表是否有环。 步骤 ： 初始化慢指针 slow 和快指针 fast 均指向头节点。 循环条件： while fast != null && fast.next != null 。 每次移动： slow = slow.next （一步）， fast = fast.next.next （两步）。 若 slow == fast ，说明存在环（快指针追上慢指针）。 原理：若无环，快指针先到达终点；有环时，快指针会从后追上慢指针。 3. 滑动窗口指针 适用场景 ：子数组/子字符串的最优解问题（如最小覆盖子串）。 示例问题 ：在数组中找到和≥target的最短连续子数组。 步骤 ： 初始化左右指针 left=0, right=0 ，当前和 sum=0 ，最小长度 min_len=∞ 。 右指针向右移动，累加 sum += nums[right] 。 当 sum ≥ target 时，记录当前长度，左指针右移并更新 sum ，直到 sum < target 。 重复步骤2-3直到右指针到达末尾。 三、关键优化点 单调性保证 ：在有序数组中，左右指针的移动方向依赖数据有序性，确保不会错过解。 避免重复计算 ：滑动窗口通过调整边界而非重新计算整体和来优化。 空间复杂度 ：通常为O(1)，仅需常数空间存储指针。 四、常见变形问题 三数之和 ：固定一个数，转化为两数之和问题（需去重）。 链表的中间节点 ：快指针到终点时，慢指针正好在中点。 无重复字符的最长子串 ：用哈希集合配合滑动窗口记录字符出现位置。 五、总结 双指针技巧通过指针的智能移动将问题规模线性化，需根据数据结构的特性（有序性、链表结构）选择指针移动策略。掌握左右指针、快慢指针和滑动窗口的适用场景，能高效解决一系列经典面试问题。