十九、双指针
访问 www.coding-time.cn 阅读原文动画效果，体验更佳。
1.双指针技巧的详解
双指针技巧是一个经常在各类算法题目中出现的解决问题的策略。这种策略主要用于解决需要在一个线性结构（例如数组或链表）中查找、修改或比较元素的问题。双指针技巧通常用于优化暴力求解或其他高复杂度解法，减少时间和空间复杂度。
1）双指针的主要应用
以下是双指针技巧的主要应用：
- 对撞指针：两个指针从不同的方向向中间移动，通常用于有序数组或链表的问题，例如「两数之和」、「反转字符串」。
- 快慢指针：两个指针以不同的速度移动，通常用于链表问题，例如「检测环」、「找到中点」。
- 滑动窗口：两个指针维护一个窗口，通常用于数组或链表的连续或固定大小子序列问题，例如「无重复字符的最长子串」、「最小覆盖子串」。
2）算法框架
以下是一个一般性的双指针技巧的算法框架：
function doublePointer(arr) { let left = 0, right = 0; let ans = ...; // 根据具体问题确定初始值 while (right < arr.length) { // 根据具体问题更新答案 // ... // 移动右指针 right++; while (/*根据具体问题确定左指针何时移动的条件*/) { // 移动左指针 left++; } } return ans; }
注意，这个框架可能需要根据具体问题进行一些微调。
3）双指针技巧的应用举例
以下是双指针技巧在不同问题上的应用：
a）对撞指针：「反转字符串」
function reverseString(s) { let left = 0, right = s.length - 1; while (left < right) { let temp = s[left]; s[left++] = s[right]; s[right--] = temp; } }
b）快慢指针：「寻找链表中点」
function middleNode(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; }
c）滑动窗口：「无重复字符的最长子串」
function lengthOfLongestSubstring(s) { let map = {}; let longest = 0; let start = 0; for (let i = 0; i < s.length; i++) { let char = s[i]; if (map[char] !== undefined) { start = Math.max(start, map[char] + 1); } map[char] = i; longest = Math.max(longest, i - start + 1); } return longest; }
带你读《图解算法小抄》十九、双指针（2）https://developer.aliyun.com/article/1348033?groupCode=tech_library
