引言

在刷完代码随想录、了解了基本的数据结构后，让我们学算法（时隔四个月了）。
阅读本篇可对基础的双指针算法有深入理解。

简单来说，解决算法问题我们可以遵循一些简单的模板，确认步骤、找合适的数据结构，解。

1 双指针：Two Pointers

什么是“双指针”模式？它主要想解决什么问题？

双指针核心是减少遍历，优化时间复杂度。
主要是为了将暴力解法中 O(n²) 的时间复杂度（两层循环）优化到 O(n)（一层循环）。它本身就是一种 O(n) 的解法。

“左右指针”和“快慢指针”这两种方法，在使用场景上最大的区别是什么？（比如，一个通常用在什么数据结构上，另一个用在什么上？一个对原始数据有什么要求？）

左右指针主要适用于有序数组(不是非要有序数组)，适用于搜索精确值。
快慢指针核心在于利用速度差来解决问题，用来解决数据结构中位置和环路的问题。
最经典的应用场景是链表，而不是数组。

1.1 左右指针

左右指针主要使用与有序数组，也通用于数组。
因为左右指针的条件判断对于位置信息有要求，需要有效移动位置。

LeetCode:
125. 验证回文串
简单的回文字符串判断。利用双指针快速遍历，优化时间复杂度。

11. 盛最多水的容器
明白移动短板是收益最高的选项后，利用双指针移动短板。
这里除了双指正还需要注意的是，我们写解答时，要尽量分开状态处理和状态转移。

错误示例

class Solution {/**移动短板，因为短板没有潜力了*/public int maxArea(int[] height) {int length = height.length;int left = 0;int right =length-1;int currentArea = Math.min(height[left],height[right]) * ( right-left);;while(left < right){if(height[left] < height[right]){left ++;}else{right --;}int tempArea = Math.min(height[left],height[right]) * ( right-left);currentArea = tempArea > currentArea? tempArea:currentArea;}return currentArea;}
}

正确示例

class Solution {public int maxArea(int[] height) {int maxArea = 0;int left = 0;int right = height.length - 1;while (left < right) {// 1. 先用当前的 left 和 right 计算面积int currentWidth = right - left;int currentHeight = Math.min(height[left], height[right]);int currentArea = currentWidth * currentHeight;// 2. 更新历史最大面积maxArea = Math.max(maxArea, currentArea);// 3. 然后再根据短板移动指针，为下一次循环做准备if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}

这样修改后，循环体内部的逻辑非常纯粹：对于当前的 left 和 right 状态，我们先计算它的面积并更新 maxArea，然后再决定下一步怎么走。每一步都处理一个独立的状态，非常清晰。

1.2 滑动窗口

滑动窗口模式，顾名思义，就像有一个大小可变的“窗口”在一个序列（通常是数组或字符串）上滑动。它也是用两个指针来定义的，通常我们叫它们 left 和 right，但这里的 left 和 right 都从起点开始，共同构成一个窗口 [left, right) 或 [left, right]。

这个模式专门用来解决“连续子数组”或“连续子字符串”的相关问题，例如：

找到满足某条件的最长/最短的连续子串。
找到所有满足某条件的连续子数组的数量。

和左右指针定初始位置、判断条件往相反的方向走不同。
滑动窗口是两个指针相同一个方向移动：

窗口扩大： 不断移动 right 指针，让新的元素进入窗口。
更新状态： 每当新元素进入，就更新窗口内的信息（例如：窗口内元素的和、不同字符的数量等）。
判断收缩： 当窗口内的状态不再满足题目要求时（或者说，满足了收缩条件时），就需要移动 left 指针，将元素移出窗口，这个过程叫作窗口收缩。
持续收缩： 持续移动 left 指针，直到窗口内的状态再次满足题目要求。
重复以上过程，直到 right 指针到达序列末尾。

3. 无重复字符的最长子串

import java.util.HashSet;
import java.util.Set;class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length();if (n == 0) {return 0;}// 1. 初始化Set<Character> charSet = new HashSet<>();int maxLen = 0;int left = 0; // 窗口左边界int right = 0; // 窗口右边界// 2. 循环，让 right 指针作为主导，探索整个字符串while (right < n) {// 3. 尝试扩大窗口：检查 right 指向的字符是否已在窗口中char charToadd = s.charAt(right);// 4. 如果有重复，触发窗口收缩//    注意这里是 while 循环，因为可能需要收缩多次while (charSet.contains(charToadd)) {// 从 Set 中移除 left 指向的字符charSet.remove(s.charAt(left));// 收缩窗口left++;}// 5. 此时窗口内一定没有重复了，可以安全地加入新字符charSet.add(charToadd);// 6. 更新最大长度//    每一次扩大窗口后，都计算一下当前长度，并尝试更新最大值maxLen = Math.max(maxLen, right - left + 1);// 7. 真正地扩大窗口，为下一次循环做准备right++;}return maxLen;}
}