双指针算法的高级用法及示例
双指针是一种常用的算法技巧，通常用于数组或链表的操作中。在一些情况下，我们可能需要使用双指针的高级用法来解决问题。在本文中，我将介绍双指针的高级用法，并提供一些 JavaScript 示例代码来帮助你理解。
- 快慢指针
快慢指针是一种双指针的高级用法，它通常用于链表的操作中。快指针和慢指针同时从链表的头部开始遍历，快指针每次遍历两个节点，慢指针每次遍历一个节点。当快指针遍历到链表尾部时，慢指针指向的节点就是链表的中间节点。
这种方法的应用场景非常广泛，例如可以用来判断链表是否有环，找到链表的中间节点等等。下面是一个示例代码：
class ListNode {constructor(val, next = null) {this.val = val;this.next = next;}
}function findMiddleNode(head) {let fast = head;let slow = head;while (fast !== null && fast.next !== null) {fast = fast.next.next;slow = slow.next;}return slow;
}const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;console.log(findMiddleNode(node1)); // Output: {val: 3, next: {val: 4, next: {val: 5, next: null}}}
- 滑动窗口
滑动窗口是一种双指针的高级用法，它通常用于字符串或数组的操作中。滑动窗口指的是一个固定大小的窗口，在字符串或数组中从左往右滑动，窗口内的内容不断发生变化。
滑动窗口可以用于解决一些字符串或数组的问题，例如找到字符串中的最长子串或最短子串等。下面是一个示例代码：
function findSubstring(s, t) {const result = [];if (!s || !t || s.length < t.length) {return result;}const map = new Map();for (let c of t) {map.set(c, map.has(c) ? map.get(c) + 1 : 1);}let left = 0,right = 0,count = t.length;while (right < s.length) {const d = s[right];if (map.has(d) && map.get(d) > 0) {count--;}map.set(d, map.get(d) - 1);right++;if (count === 0) {const leftChar = s[left];if (map.has(leftChar) && map.get(leftChar) >= 0) {count++;}map.set(leftChar, map.get(leftChar) + 1);if (right - left === t.length) {result.push(left);}left++;}}return result;
}console.log(findSubstring("barfoothefoobarman", "foo")); // Output: [0, 9]
在上面的示例代码中，我们使用滑动窗口来查找字符串 s 中包含字符串 t 中所有字符的子串的起始位置。我们使用 map 来记录字符串 t 中每个字符出现的次数，并且使用 left 和 right 变量来记录窗口的左右边界，使用 count 变量来记录当前窗口内还需要找到多少个字符。
当我们移动右边界时，我们不断地减少 map 中对应字符的数量，如果这个字符在 map 中存在并且数量大于 0，那么说明我们已经找到了一个需要找的字符，count 就要减 1。当 count 减少到 0 时，说明当前窗口已经包含了字符串 t 中所有字符，此时我们移动左边界，直到窗口不再包含字符串 t 中所有字符，然后继续移动右边界。我们不断地维护这个过程，直到右边界到达字符串 s 的末尾。最后，我们返回所有找到的子串的起始位置。
总结
双指针是一种非常实用的算法技巧，可以用于解决许多数组和链表的问题。在一些情况下，我们可能需要使用双指针的高级用法，例如快慢指针和滑动窗口。本文介绍了双指针的高级用法，并提供了 JavaScript 示例代码，希望能够帮助你更好地理解和应用双指针算法。
