网站开发算法信息网站 微站

双指针法的核心思想是通过同时操作两个指针来遍历数据结构，通常是数组或链表，以达到优化算法性能的目的。具体来说，双指针法能够减少时间复杂度、空间复杂度，或者简化逻辑结构。以下是双指针法的几个核心思想：
ps 下面提到的“应用场景”：在力扣中都有原题！

1. 两端逼近：

• 核心思想：通过设置两个指针，一个从数据结构的左端开始，一个从右端开始，然后根据一定的条件向中间移动这两个指针，从而逐步缩小问题的规模。
• 应用场景：如数组中的“二分搜索”、“盛水最多的容器（Container with Most Water）”、以及“接雨水（Trapping Rain Water）”等问题。
• 优势：避免了多次嵌套循环或者重复遍历，从而将时间复杂度从 O(n^2) 降到 O(n)。

2. 快慢指针：

• 核心思想：设置两个指针，一个指针每次移动一步（慢指针），另一个指针每次移动两步或更多（快指针）。通过这种方式，可以在一次遍历中同时完成多项任务。
• 应用场景：如链表中的“环检测（Cycle Detection）”问题、寻找链表的中间节点等。
• 优势：通过一次遍历同时获取多种信息，提高了效率。

3. 滑动窗口：

• 核心思想：使用两个指针定义一个窗口，窗口可以向前滑动以覆盖不同的子区间。这种方法常用于解决涉及子数组或子字符串的问题，如“最长子串”、“最小覆盖子串”等。
• 应用场景：如“最小覆盖子串（Minimum Window Substring）”、“无重复字符的最长子串（Longest Substring Without Repeating Characters）”等。
• 优势：在处理连续子区间问题时，可以在 O(n) 时间复杂度内完成解决方案。

4. 分割与合并：

• 核心思想：将问题分解为左右两部分，通过双指针分别处理这两部分，并在合适的时候合并结果。
• 应用场景：如“归并排序（Merge Sort）”、“两个有序数组的合并”等。
  优势：可以有效处理有序数组或链表的合并问题，保证合并后的结果依然有序。

5. 条件判断与指针移动：

• 核心思想：通过条件判断决定哪个指针移动，以逐步逼近或找到符合条件的解。
• 应用场景：如“二分查找”、“两数之和（Two Sum）”问题。
• 优势：能够快速收敛到问题的解，避免不必要的遍历和计算。

总结：

双指针法的核心在于利用两个指针的协作，通过合理的移动策略来减少问题的规模或提高问题的求解效率。其应用非常广泛，可以显著优化涉及数组、链表等线性结构的问题，尤其在需要高效处理子区间、子序列、或寻找特定条件下的元素时尤为有效。

这种方法的优势在于线性遍历能够在保持结果正确性的同时，减少算法的复杂度，是处理各种线性问题时的一个非常有力的工具。

例题：力扣接雨水接雨水


双指针代码+详细注释：

• 重点1，利用双指针的好处就是自然完成遍历！（两个指针相交就便利完成）
• 重点2：按列来计算！

class Solution {
public:int trap(vector<int>& height) {// 获取数组的长度int n = height.size();// 如果数组为空，则没有可以积水的地方，直接返回0if (n == 0) return 0;// 初始化两个指针，分别指向数组的两端int left = 0, right = n - 1;// 初始化左边和右边的最大高度int leftMax = 0, rightMax = 0;// 初始化结果，存储最终的积水量int waterTrapped = 0;// 当左指针小于右指针时，继续循环while (left < right) {// 如果左边的高度小于右边的高度，则说明左边可以计算水洼if (height[left] < height[right]) {// 如果当前左边的高度大于或等于leftMax，则更新leftMaxif (height[left] >= leftMax) {leftMax = height[left];} else {// 否则，则必定形成小水洼！计算当前左边位置能存储的水量，并累加到waterTrapped中waterTrapped += leftMax - height[left];}// 左指针向右移动left++;} else {// 如果右边的高度小于或等于左边的高度if (height[right] >= rightMax) {// 如果当前右边的高度大于或等于rightMax，则更新rightMaxrightMax = height[right];} else {// 否则，计算当前右边位置能存储的水量，并累加到waterTrapped中waterTrapped += rightMax - height[right];}// 右指针向左移动right--;}}// 返回计算得到的总积水量return waterTrapped;}
};