尧图网页设计 
1. 双指针算法的本质与应用场景双指针算法是解决数组/链表类问题的经典技巧其核心思想是通过两个指针的协同移动来降低时间复杂度。不同于暴力解法中常见的O(n²)复杂度双指针通常能将复杂度优化到O(n)。这种算法在LeetCode题库中出现的频率极高特别是在处理有序数据时效果显著。我在刷题过程中发现双指针主要有三种典型应用模式对撞指针首尾指针常用于有序数组的两数之和、三数之和等问题快慢指针解决链表环检测、中点查找等场景滑动窗口处理子串/子数组相关问题新手常见误区是认为双指针必须严格两个指针实际上指针可以是多个关键在于是通过指针的相对移动来优化遍历过程。2. 经典例题解析对撞指针实战2.1 两数之和IILeetCode 167这是最基础的对撞指针应用。给定升序数组numbers和目标值target找到两个数使它们的和等于target。vectorint twoSum(vectorint 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 {}; }关键点在于初始化时left指向首元素right指向末元素根据当前和与target的比较决定移动哪个指针时间复杂度从暴力解的O(n²)降到O(n)2.2 三数之和LeetCode 15进阶版的对撞指针应用需要先排序数组vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; for (int i 0; i nums.size(); i) { if (i 0 nums[i] nums[i-1]) continue; // 去重 int left i 1, right nums.size() - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left1]) left; // 跳过重复 while (left right nums[right] nums[right-1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return res; }这个解法有几个精妙之处先排序确保可以使用双指针外层循环固定第一个数内层用双指针找另外两个数通过跳过重复元素来优化性能3. 快慢指针的魔法应用3.1 环形链表检测LeetCode 141快慢指针是检测环的经典方法快指针每次走两步慢指针每次走一步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; }这个算法的精妙之处在于如果有环快指针最终会追上慢指针时间复杂度O(n)空间复杂度O(1)不需要额外存储空间优于哈希表解法3.2 链表中点查找快慢指针的另一个典型应用是快速找到链表的中点ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }这个技巧在链表归并排序等场景非常有用只需要一次遍历就能找到中点。4. 滑动窗口技巧详解4.1 无重复字符的最长子串LeetCode 3滑动窗口是双指针的一种特殊形式用于解决子串问题int lengthOfLongestSubstring(string s) { unordered_setchar window; int left 0, max_len 0; for (int right 0; right s.size(); right) { while (window.count(s[right])) { window.erase(s[left]); left; } window.insert(s[right]); max_len max(max_len, right - left 1); } return max_len; }这个实现有几个关键点使用哈希集合记录窗口内的字符当遇到重复字符时移动左指针直到消除重复始终保持窗口内无重复字符4.2 最小覆盖子串LeetCode 76更复杂的滑动窗口应用需要统计字符出现次数string minWindow(string s, string t) { unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0; int valid 0; int start 0, len INT_MAX; while (right s.size()) { char c s[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } while (valid need.size()) { if (right - left len) { start left; len right - left; } char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return len INT_MAX ? : s.substr(start, len); }这个解法展示了滑动窗口处理复杂条件的典型模式使用两个哈希表分别记录需要匹配的字符和当前窗口的字符valid变量跟踪匹配进度在满足条件时尝试收缩窗口5. 双指针算法优化技巧5.1 指针移动条件的优化在实际编码中指针移动条件可以进一步优化。例如在盛最多水的容器问题LeetCode 11中int maxArea(vectorint height) { int left 0, right height.size() - 1; int res 0; while (left right) { res max(res, min(height[left], height[right]) * (right - left)); if (height[left] height[right]) { left; } else { right--; } } return res; }这里移动较矮的一边的指针因为移动较高的指针不可能得到更大的面积。5.2 多指针协同工作有些问题需要超过两个指针协同工作比如颜色分类LeetCode 75void sortColors(vectorint nums) { int p0 0, p2 nums.size() - 1; int curr 0; while (curr p2) { if (nums[curr] 0) { swap(nums[curr], nums[p0]); } else if (nums[curr] 2) { swap(nums[curr], nums[p2--]); } else { curr; } } }这个解法使用三个指针p0跟踪0的右边界p2跟踪2的左边界curr是当前遍历指针6. 常见错误与调试技巧6.1 指针越界问题双指针算法最常见的错误就是指针越界。例如在二分查找变种问题中int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 注意是而不是 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }常见错误包括循环条件写成left right导致漏判边界情况mid计算使用(leftright)/2可能导致整数溢出指针移动时忘记1/-1导致死循环6.2 滑动窗口边界处理滑动窗口的边界条件需要特别注意// 错误示例容易漏掉某些情况 for (int right 0; right s.size(); right) { while (invalidCondition) { left; } // 处理逻辑 } // 正确写法应该明确窗口的维护条件 while (right s.size()) { // 扩展右边界 right; // 更新窗口状态 // 收缩左边界 while (windowNeedShrink) { // 更新窗口状态 left; } }7. 性能优化实战7.1 减少不必要的计算在遍历过程中有些计算可以提前或延迟执行来优化性能。例如在接雨水问题LeetCode 42中int trap(vectorint 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; }这个解法通过动态维护左右最大值避免了重复计算。7.2 利用数据特性优化有些问题可以利用输入数据的特性进一步优化。例如在移动零问题LeetCode 283中void moveZeroes(vectorint nums) { int lastNonZero 0; for (int i 0; i nums.size(); i) { if (nums[i] ! 0) { swap(nums[lastNonZero], nums[i]); } } }这个解法利用了所有非零元素相对顺序不变的特点只需要一次遍历就能完成任务。8. 复杂问题拆解技巧8.1 多步双指针组合有些复杂问题需要组合多种双指针技巧。例如在删除排序数组中的重复项IILeetCode 80中int removeDuplicates(vectorint nums) { int n nums.size(); if (n 2) return n; int slow 2, fast 2; while (fast n) { if (nums[slow-2] ! nums[fast]) { nums[slow] nums[fast]; slow; } fast; } return slow; }这个解法结合了快慢指针和固定间隔检查允许每个元素最多出现两次。8.2 与其它算法结合双指针经常需要与其它算法结合使用。例如在回文链表LeetCode 234中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, *curr slow; while (curr) { ListNode *next curr-next; curr-next prev; prev curr; curr next; } // 比较前后两部分 ListNode *p1 head, *p2 prev; while (p2) { if (p1-val ! p2-val) return false; p1 p1-next; p2 p2-next; } return true; }这个解法综合运用了快慢指针找中点、链表反转和双指针比较三种技巧。 双指针算法：原理、应用与LeetCode实战
1. 双指针算法的本质与应用场景双指针算法是解决数组/链表类问题的经典技巧其核心思想是通过两个指针的协同移动来降低时间复杂度。不同于暴力解法中常见的O(n²)复杂度双指针通常能将复杂度优化到O(n)。这种算法在LeetCode题库中出现的频率极高特别是在处理有序数据时效果显著。我在刷题过程中发现双指针主要有三种典型应用模式对撞指针首尾指针常用于有序数组的两数之和、三数之和等问题快慢指针解决链表环检测、中点查找等场景滑动窗口处理子串/子数组相关问题新手常见误区是认为双指针必须严格两个指针实际上指针可以是多个关键在于是通过指针的相对移动来优化遍历过程。2. 经典例题解析对撞指针实战2.1 两数之和IILeetCode 167这是最基础的对撞指针应用。给定升序数组numbers和目标值target找到两个数使它们的和等于target。vectorint twoSum(vectorint 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 {}; }关键点在于初始化时left指向首元素right指向末元素根据当前和与target的比较决定移动哪个指针时间复杂度从暴力解的O(n²)降到O(n)2.2 三数之和LeetCode 15进阶版的对撞指针应用需要先排序数组vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; for (int i 0; i nums.size(); i) { if (i 0 nums[i] nums[i-1]) continue; // 去重 int left i 1, right nums.size() - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.push_back({nums[i], nums[left], nums[right]}); while (left right nums[left] nums[left1]) left; // 跳过重复 while (left right nums[right] nums[right-1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return res; }这个解法有几个精妙之处先排序确保可以使用双指针外层循环固定第一个数内层用双指针找另外两个数通过跳过重复元素来优化性能3. 快慢指针的魔法应用3.1 环形链表检测LeetCode 141快慢指针是检测环的经典方法快指针每次走两步慢指针每次走一步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; }这个算法的精妙之处在于如果有环快指针最终会追上慢指针时间复杂度O(n)空间复杂度O(1)不需要额外存储空间优于哈希表解法3.2 链表中点查找快慢指针的另一个典型应用是快速找到链表的中点ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }这个技巧在链表归并排序等场景非常有用只需要一次遍历就能找到中点。4. 滑动窗口技巧详解4.1 无重复字符的最长子串LeetCode 3滑动窗口是双指针的一种特殊形式用于解决子串问题int lengthOfLongestSubstring(string s) { unordered_setchar window; int left 0, max_len 0; for (int right 0; right s.size(); right) { while (window.count(s[right])) { window.erase(s[left]); left; } window.insert(s[right]); max_len max(max_len, right - left 1); } return max_len; }这个实现有几个关键点使用哈希集合记录窗口内的字符当遇到重复字符时移动左指针直到消除重复始终保持窗口内无重复字符4.2 最小覆盖子串LeetCode 76更复杂的滑动窗口应用需要统计字符出现次数string minWindow(string s, string t) { unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0; int valid 0; int start 0, len INT_MAX; while (right s.size()) { char c s[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } while (valid need.size()) { if (right - left len) { start left; len right - left; } char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return len INT_MAX ? : s.substr(start, len); }这个解法展示了滑动窗口处理复杂条件的典型模式使用两个哈希表分别记录需要匹配的字符和当前窗口的字符valid变量跟踪匹配进度在满足条件时尝试收缩窗口5. 双指针算法优化技巧5.1 指针移动条件的优化在实际编码中指针移动条件可以进一步优化。例如在盛最多水的容器问题LeetCode 11中int maxArea(vectorint height) { int left 0, right height.size() - 1; int res 0; while (left right) { res max(res, min(height[left], height[right]) * (right - left)); if (height[left] height[right]) { left; } else { right--; } } return res; }这里移动较矮的一边的指针因为移动较高的指针不可能得到更大的面积。5.2 多指针协同工作有些问题需要超过两个指针协同工作比如颜色分类LeetCode 75void sortColors(vectorint nums) { int p0 0, p2 nums.size() - 1; int curr 0; while (curr p2) { if (nums[curr] 0) { swap(nums[curr], nums[p0]); } else if (nums[curr] 2) { swap(nums[curr], nums[p2--]); } else { curr; } } }这个解法使用三个指针p0跟踪0的右边界p2跟踪2的左边界curr是当前遍历指针6. 常见错误与调试技巧6.1 指针越界问题双指针算法最常见的错误就是指针越界。例如在二分查找变种问题中int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 注意是而不是 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }常见错误包括循环条件写成left right导致漏判边界情况mid计算使用(leftright)/2可能导致整数溢出指针移动时忘记1/-1导致死循环6.2 滑动窗口边界处理滑动窗口的边界条件需要特别注意// 错误示例容易漏掉某些情况 for (int right 0; right s.size(); right) { while (invalidCondition) { left; } // 处理逻辑 } // 正确写法应该明确窗口的维护条件 while (right s.size()) { // 扩展右边界 right; // 更新窗口状态 // 收缩左边界 while (windowNeedShrink) { // 更新窗口状态 left; } }7. 性能优化实战7.1 减少不必要的计算在遍历过程中有些计算可以提前或延迟执行来优化性能。例如在接雨水问题LeetCode 42中int trap(vectorint 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; }这个解法通过动态维护左右最大值避免了重复计算。7.2 利用数据特性优化有些问题可以利用输入数据的特性进一步优化。例如在移动零问题LeetCode 283中void moveZeroes(vectorint nums) { int lastNonZero 0; for (int i 0; i nums.size(); i) { if (nums[i] ! 0) { swap(nums[lastNonZero], nums[i]); } } }这个解法利用了所有非零元素相对顺序不变的特点只需要一次遍历就能完成任务。8. 复杂问题拆解技巧8.1 多步双指针组合有些复杂问题需要组合多种双指针技巧。例如在删除排序数组中的重复项IILeetCode 80中int removeDuplicates(vectorint nums) { int n nums.size(); if (n 2) return n; int slow 2, fast 2; while (fast n) { if (nums[slow-2] ! nums[fast]) { nums[slow] nums[fast]; slow; } fast; } return slow; }这个解法结合了快慢指针和固定间隔检查允许每个元素最多出现两次。8.2 与其它算法结合双指针经常需要与其它算法结合使用。例如在回文链表LeetCode 234中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, *curr slow; while (curr) { ListNode *next curr-next; curr-next prev; prev curr; curr next; } // 比较前后两部分 ListNode *p1 head, *p2 prev; while (p2) { if (p1-val ! p2-val) return false; p1 p1-next; p2 p2-next; } return true; }这个解法综合运用了快慢指针找中点、链表反转和双指针比较三种技巧。