双指针-leetcode算法题总结+练习
1. 常考类型
2. 解题思路（按题型给“可直接执行”的步骤）
2.1 左右夹近（数组已排序或可排序）
二数/三数之和 & 面积类
-
若题目允许，先排序（可能改变原顺序要先确认题意）。
-
设
l=0, r=n-1；根据目标函数选择移动方向：-
和太小 →
l++；和太大 →r--。 -
面积/距离最值 → 每步计算答案，同时按规则收缩较差的一侧。
-
-
三数之和：外层枚举
i，内层对l=i+1, r=n-1夹逼，并在相等时跳重。 -
收集/更新答案，直到
l>=r（或外层循环结束）。
简模板（Two Sum II / 有序）：
int l = 0, r = nums.length - 1;while (l < r) { int sum = nums[l] + nums[r]; if (sum == target) return new int[]{l+1, r+1}; if (sum < target) l++; else r--;}三数之和（去重！）：
Arrays.sort(nums);int n = nums.length;List<List> ans = new ArrayList();for (int i = 0; i 0 && nums[i] == nums[i-1]) continue; int l = i + 1, r = n - 1; while (l < r) { long s = (long)nums[i] + nums[l] + nums[r]; if (s == 0) { ans.add(Arrays.asList(nums[i], nums[l], nums[r])); while (l < r && nums[l] == nums[l+1]) l++; while (l < r && nums[r] == nums[r-1]) r--; l++; r--; } else if (s < 0) l++; else r--; }}回文串（125）：
-
l=0, r=n-1；跳过非字母数字。 -
比较同一大小写；相等则双向收缩；不等返回
false。 -
走完返回
true。
int l = 0, r = s.length()-1;while (l < r) { while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++; while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--; if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false; l++; r--;}return true;2.2 快慢指针（链表）
判环与入口（141/142）
-
slow=head, fast=head；fast每次两步、slow一步。 -
相遇则有环；无相遇到尾则无环。
-
找入口：
p1=head, p2=相遇点同速前进，相遇处即入口。
倒数第 k 个（19 的子步骤）
-
fast先走k步； -
fast/slow同步走到fast==null；slow即倒数第 k。 -
若要删除：用哑节点
dummy，定位到slow的前驱再改指针。
原地删除看“下一位”（203/237）
-
用
dummy；cur=dummy； -
循环条件
cur.next != null； -
若
cur.next.val==val删之，否则cur=cur.next（删除时不前进）。
2.3 滑动窗口（子串/子数组）
最长无重复子串（3）
-
右指针
r扩张，把s[r]放入计数； -
若违反要求（出现重复），移动左指针
l，边移边减少计数直到合法； -
每次合法时更新答案
max = max(max, r-l+1)。
int[] cnt = new int[128];int l = 0, ans = 0;for (int r = 0; r 1) { cnt[s.charAt(l)]--; l++; } ans = Math.max(ans, r - l + 1);}最小覆盖子串（76）
-
统计目标串
t的频率need；维护window+have/needMatch。 -
右扩纳入字符；当
window覆盖need时，尽量左缩并更新最优区间。 -
返回最短区间。
（实现与你现有熟悉模板一致，这里略。）
长度最小子数组（209）
-
sum += nums[r]右扩； -
当
sum >= target，不断左缩并更新ans； -
结束返回
ans或 0。
int l = 0, sum = 0, ans = Integer.MAX_VALUE;for (int r = 0; r = target) { ans = Math.min(ans, r - l + 1); sum -= nums[l++]; }}return ans == Integer.MAX_VALUE ? 0 : ans;2.4 同向读写指针
去重（26：保留一个）
-
w=0写指针； -
枚举
x：若是首元素或x != nums[w-1]，写入并w++； -
返回
w。
int w = 0;for (int x : nums) if (w == 0 || x != nums[w-1]) nums[w++] = x;return w;去重（80：最多保留两次）
int w = 0;for (int x : nums) if (w < 2 || x != nums[w-2]) nums[w++] = x;return w;移除元素（27：不保序最快）
int l = 0, r = n - 1;while (l <= r) { if (nums[l] == val) nums[l] = nums[r--]; else l++;}return r + 1;2.5 双序列双指针
合并两个有序数组（88，尾填避免搬运）
-
i=m-1, j=n-1, k=m+n-1； -
从大到小把较大者放到
k； -
直到
j<0结束。
int i=m-1, j=n-1, k=m+n-1;while (j >= 0) { if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--]; else nums1[k--] = nums2[j--];}区间交集（986）
-
两列表各用一指针；
-
取交集
[max(a.start,b.start), min(a.end,b.end)]若合法则加入； -
谁结束早，谁指针前进。
3. 易错点清单
-
边界：
while (l < r)vs<=；三数之和外层/内层去重顺序。 -
删除时不前进：链表用“看下一位”，否则会漏删连续目标。
-
滑窗更新时机：最长类“合法后更新”；最短类“每次缩时更新”。
-
排序副作用：是否允许改变原序；涉及索引时要保留原位信息。
-
整型溢出：求和/面积用
long。 -
空/单元素：链表
head==null、数组长度 0/1 要先处理。
4. leetcode练习题
27 移除元素
示例 1：
输入：nums = [3,2,2,3], val = 3输出：2, nums = [2,2,_,_]解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
class Solution { public int removeElement(int[] nums, int val) { int left =0; for(int i =0; i<nums.length; i++){ if(nums[i] != val){ nums[left] = nums[i]; left++; } } return left; }}
