双指针基础概念
双指针技术通常用于数组或链表等线性结构中，通过两个指针协同遍历来优化时间复杂度。主要分为以下类型：
- 同向指针：两个指针从同一侧出发，移动速度不同
- 对向指针：两个指针分别从首尾向中间移动
- 快慢指针：常用于环形链表检测
同向指针应用
移除重复元素
给定排序数组，原地移除重复元素并返回新长度。
int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int slow = 0; for(int fast = 1; fast < nums.size(); ++fast){ if(nums[fast] != nums[slow]){ nums[++slow] = nums[fast]; } } return slow + 1; }练习题1：移除指定值
给定数组nums和值val，原地移除所有val实例。
练习题2：合并两个有序数组
将nums2合并到nums1中，假设nums1有足够空间。
对向指针应用
两数之和II
在有序数组中找出两个数使它们的和等于目标值。
vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; while(left < right){ int sum = numbers[left] + numbers[right]; if(sum == target) return {left+1, right+1}; else if(sum < target) left++; else right--; } return {}; }练习题3：盛最多水的容器
给定高度数组，找出两条线使得容器能盛最多水。
练习题4：三数之和
找出数组中所有和为0的三元组。
快慢指针应用
环形链表检测
判断链表中是否有环。
bool hasCycle(ListNode *head) { ListNode *slow = head, *fast = head; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; }练习题5：寻找环形入口
给定有环链表，返回环的起始节点。
练习题6：链表中点
找到链表的中间节点（偶数时返回第二个）。
滑动窗口变种
最小覆盖子串
在字符串S中找到包含T所有字符的最短子串。
string minWindow(string s, string t) { unordered_map<char, int> need; for(char c : t) need[c]++; int left = 0, cnt = 0, min_len = INT_MAX, start = 0; for(int right = 0; right < s.size(); ++right){ if(need[s[right]]-- > 0) cnt++; while(cnt == t.size()){ if(right - left + 1 < min_len){ min_len = right - left + 1; start = left; } if(++need[s[left]] > 0) cnt--; left++; } } return min_len == INT_MAX ? "" : s.substr(start, min_len); }练习题7：字符串排列
判断s2是否包含s1的排列。
练习题8：无重复字符的最长子串
多序列指针
合并K个排序链表
使用优先队列优化多指针比较。
struct Compare { bool operator()(ListNode* a, ListNode* b){ return a->val > b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, Compare> pq; for(auto list : lists) if(list) pq.push(list); ListNode dummy(0); ListNode* tail = &dummy; while(!pq.empty()){ auto node = pq.top(); pq.pop(); tail->next = node; tail = tail->next; if(node->next) pq.push(node->next); } return dummy.next; }练习题9：两个数组的交集II
计算两个数组的交集（出现次数一致）。
练习题10：最长公共前缀
查找字符串数组中的最长公共前缀。
特殊场景应用
回文链表判断
结合快慢指针和链表反转。
bool isPalindrome(ListNode* head) { if(!head || !head->next) return true; ListNode *slow = head, *fast = head; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } ListNode *prev = nullptr; while(slow){ ListNode *next = slow->next; slow->next = prev; prev = slow; slow = next; } while(prev){ if(head->val != prev->val) return false; head = head->next; prev = prev->next; } return true; }练习题11：验证回文串
忽略非字母数字字符后判断回文。
练习题12：最短无序连续子数组
找出需要排序的最短子数组使整个数组升序。
双指针优化策略
接雨水问题
通过左右最大值指针计算积水量。
int trap(vector<int>& height) { int left = 0, right = height.size() - 1; int left_max = 0, right_max = 0; int res = 0; while(left < right){ if(height[left] < height[right]){ height[left] >= left_max ? left_max = height[left] : res += left_max - height[left]; left++; } else { height[right] >= right_max ? right_max = height[right] : res += right_max - height[right]; right--; } } return res; }练习题13：最大连续1的个数III
最多翻转K个0后的最大连续1长度。
练习题14：水果成篮
收集两种水果的最大总量（滑动窗口变种）。
指针操作技巧
链表排序
结合归并排序和快慢指针分割链表。
ListNode* sortList(ListNode* head) { if(!head || !head->next) return head; ListNode *slow = head, *fast = head->next; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; } ListNode *mid = slow->next; slow->next = nullptr; return merge(sortList(head), sortList(mid)); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode *tail = &dummy; while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; }练习题15：奇偶链表
将所有奇数节点和偶数节点分别排在一起。
练习题16：重排链表
L0→Ln→L1→Ln-1→...形式重新排列。
边界条件处理
颜色分类
荷兰国旗问题，三指针分区处理。
void sortColors(vector<int>& nums) { int low = 0, high = nums.size() - 1, mid = 0; while(mid <= high){ if(nums[mid] == 0){ swap(nums[low++], nums[mid++]); } else if(nums[mid] == 1){ mid++; } else { swap(nums[mid], nums[high--]); } } }练习题17：移动零
将所有0移动到数组末尾。
练习题18：区间列表的交集
给定两个区间列表，返回它们的交集。
综合应用实例
最长山脉数组
使用双向遍历寻找山脉峰值。
int longestMountain(vector<int>& arr) { int n = arr.size(), res = 0; vector<int> up(n, 0), down(n, 0); for(int i = n-2; i >= 0; --i){ if(arr[i] > arr[i+1]) down[i] = down[i+1] + 1; } for(int i = 1; i < n; ++i){ if(arr[i] > arr[i-1]) up[i] = up[i-1] + 1; if(up[i] && down[i]) res = max(res, up[i] + down[i] + 1); } return res >= 3 ? res : 0; }练习题19：数组中的最长湍流子数组
比较符号交替的最大子数组长度。
练习题20：统计优美子数组
恰好包含k个奇数的子数组数目。
