双指针思路总结

今天复习双指针的使用，说是“指针”，其实跟指针关系不大，更合适的是一种标记的功能；双指针算法是一种常见且高效的算法技巧，尤其适用于处理具有线性结构的问题,故于双指针解题相关的数据结构是数组和链表。双指针方法的关键核心思路可以总结为以下几种：

1. 对撞指针（Two Pointers from Both Ends）

  • 思路：将两个指针分别放在序列的两端，向中间靠拢，根据特定条件调整指针的位置，最终在某个位置相遇或交错。
  • 适用场景：常用于需要找一对元素的问题，如「盛最多水的容器」、「两数之和 II - 输入有序数组」等。
  • 例子：盛水容器问题，寻找两个指针之间最大的面积，通过比较两端的高度，移动较小高度的指针。
    链接：leetcode盛最多水的容器

这个问题是经典的「盛最多水的容器」问题，通常通过双指针的方法来解决。我们来详细分析解题思路。

1.1盛最多水的容器解题的核心思路

  1. 双指针法：从数组的两端向中间收缩，逐步逼近最大可能的面积。

  2. 面积的计算：

    • 假设我们选择了两个位置 i 和 j，它们对应的高度分别为 height[i] 和 height[j]，那么它们形成的容器的宽度为 j - i，容器的高度则由较低的那条垂直线决定，即 min(height[i], height[j])。
    • 因此，容器的面积为 面积 = (j - i) * min(height[i], height[j])。

  3. 移动指针：

    • 一开始我们选择数组的两端作为初始的指针位置，分别是 left = 0 和 right = n - 1（其中 n 是数组长度）。
    • 每次计算当前指针位置所形成的面积，然后比较并更新最大面积。
    • 然后，移动指针：为了找到更大的面积，应该移动高度较小的一侧的指针。这是因为面积取决于较短的那根垂线，只有移动较短的那一侧，可能会找到更高的垂线，从而得到更大的面积。

  4. 终止条件：

    • 当两个指针相遇时，整个过程结束，此时记录的最大面积就是最终结果。

1.2代码实现

下面是基于上述思路的代码实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;            // 左指针
        int right = height.size() - 1; // 右指针
        int max_area = 0;        // 最大面积

        while (left < right) {
            // 计算当前面积
            int current_height = min(height[left], height[right]);
            int current_width = right - left;
            int current_area = current_width * current_height;

            // 更新最大面积
            max_area = max(max_area, current_area);

            // 移动指针，选择较小的那一侧
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max_area;
    }
};

1.3示例分析

假设输入为 [1,8,6,2,5,4,8,3,7]，以下是详细的操作步骤：

  1. 初始时 left = 0，right = 8，高度分别是 1 和 7，计算面积为 min(1, 7) * (8 - 0) = 7 * 8 = 56。
  2. 因为 height[0] < height[8]，所以移动 left，即 left = 1。
  3. 此时 left = 1，right = 8，高度分别是 8 和 7，计算面积为 min(8, 7) * (8 - 1) = 7 * 7 = 49。
  4. 这时 height[1] > height[8]，所以移动 right，即 right = 7。
  5. 不断重复此过程，直到 left 和 right 相遇，最后得到的最大面积就是 49。

1.4时间复杂度和空间复杂度

  • 时间复杂度：O(n)，其中 n 是数组的长度。我们只需遍历数组一次。
  • 空间复杂度：O(1)，只使用了常数个额外空间。
    这个算法利用了双指针逼近的技巧，有效地降低了时间复杂度，是最优解法。

例题2：接雨水

接雨水解题核心思想

  • 初始化指针：left 指向数组的开始，right 指向数组的末尾，用来从两端向中心扫描。
  • 左右最大值：leftMax 和 rightMax 分别记录左侧和右侧遇到的最大高度，以确定在每个位置可能接的雨水量。
  • 循环条件：当 left 小于 right 时继续执行，这保证了不会重复计算任何位置的雨水。
  • 计算雨水：在循环中，比较 leftMax 和 rightMax 来决定是从左边更新雨水量还是从右边。选择较小的一侧进行雨水量的计算，因为这边的最大高度是制约因素（短板效应）。
  • 指针移动：移动较小一侧的指针（left 或 right），以继续对未处理的区域进行雨水量计算。

这种方法高效地利用了“木桶原理”和双指针策略，确保了在一次遍历中计算出正确的雨水总量，时间复杂度为 O(n)，空间复杂度为 O(1)。

class Solution {
public:
    int trap(vector<int>& height) {
        // 初始化左右指针
        int left = 0;
        int right = height.size() - 1;

        // 初始化左右两侧的最大值变量
        int leftMax = 0;
        int rightMax = 0;

        // 用于累加所有能接的雨水量
        int sumTrap = 0;

        // 当左指针小于右指针时循环
        while (left < right) {
            // 更新左侧的最大高度
            leftMax = max(leftMax, height[left]);
            // 更新右侧的最大高度
            rightMax = max(rightMax, height[right]);

            // 判断左侧和右侧的最大高度哪个较小
            if (leftMax < rightMax) {
                // 如果左侧的最大高度较小，则计算当前位置的雨水量，并将左指针向右移
                sumTrap += leftMax - height[left];
                left++;
            }
            else {
                // 如果右侧的最大高度较小或相等，则计算当前位置的雨水量，并将右指针向左移
                sumTrap += rightMax - height[right];
                right--;
            }
        }

        // 返回总的雨水量
        return sumTrap;
    }
};

2. 快慢指针（Slow and Fast Pointers）

  • 思路：两个指针以不同的速度遍历序列，通常一个指针一次走一步（慢指针），另一个指针一次走两步（快指针）。这种方法可以检测到特定的条件，如链表中的环或中间元素。
  • 适用场景1：常用于链表问题，如「链表环检测」、「寻找链表的中点」等。
  • 例子：在检测链表环时，快指针每次走两步，慢指针每次走一步，如果存在环，两个指针最终会相遇。环形链表
  • 适用场景2：用于数组问题，如「元素移动」和「数据分区」等。
    • 快慢指针在处理诸如将所有特定值移动到数组一端的问题中非常有用，同时保持其他元素的相对顺序；如，LeetCode 上的“移动零”问题。
    • 对于上述问题，更通用的，是快慢指针可以实现数据分区，即：快慢指针可用于将数据根据某种条件分成两部分，类似于快速排序中的分区操作。例如，根据数组元素的值将数组分为大于或小于某个特定值的两部分。
    • 数据分区实现实现方法：快指针遍历整个数组，慢指针跟踪分区的边界。当快指针指向的元素满足某个条件时（如小于给定值），将其与慢指针指向的元素交换，然后慢指针向前移动一步。这样，慢指针左边的所有元素都满足条件，右边的不满足。

对于“移动零问题”代码如下：

	class Solution {
	public:
	    void moveZeroes(vector<int>& nums) {
	        int left = 0;
	        for (int i = 0; i < nums.size(); i++) {
	            if (nums[i] != 0) {
	                if (left != i) {  // 只在需要时才交换
	                    swap(nums[left], nums[i]);
	                }
	                left++;
	            }
	        }
	    }
	};

下面是将上述代码与快慢指针的概念联系起来的分析：

快慢指针的定义：

  • 慢指针（left）：在这段代码中，left 指针充当慢指针的角色。它指向的是下一个非零元素应该存放的位置。
  • 快指针（i 或 right）：i（代码中的循环变量）实际上充当了快指针的角色，它遍历数组中的每个元素，寻找非零元素。

快慢指针的工作方式：

  • 初始化：left 和 right 都从数组的起始位置开始，left 慢指针指向下一个非零元素将要放置的位置，right 快指针指向当前正在处理的元素，这里用for循环中的i代替。
  • 遍历和比较：
    • 快指针 i 每次移动一步，检查当前元素 nums[i] 是否为非零。
    • 如果 nums[i] 是非零元素，直接互换慢指针 nums[left] 与快指针nums[i]，慢指针并向前移动一位，循环继续。

总结

  • 使用快慢指针技术，其中 i 是快指针，left 是慢指针，有效地将数组中的非零元素移动到数组前端，同时将所有零元素移到数组后端，保持了 O(n) 的时间复杂度和 O(1) 的空间复杂度。

快慢指针的常见解题总结：

快慢指针在数组与链表中的应用涵盖了很多实际问题，如循环检测、元素移动和数据分区等。下面具体说明这些应用场景：

  1. 检测链表中的环：
    快慢指针从链表的头部出发，慢指针每次移动一个节点，快指针每次移动两个节点。如果链表中存在环，则快指针最终会追上慢指针（即两者会相遇）。如果链表中没有环，则快指针会达到链表的末尾。

  2. 找到链表的中间节点：
    快慢指针从链表的头部出发，慢指针每次移动一个节点，快指针每次移动两个节点。当快指针到达链表的末尾时，慢指针正好在链表的中间位置。这个技巧可以用来在单次遍历中找到链表的中间节点，常用于链表的分割、归并排序等问题。

  3. 找到链表的倒数第 k 个节点：
    快慢指针都从链表的头部出发，但快指针先向前移动 k 步。然后两个指针以相同的速度同时向前移动。当快指针到达链表的末尾时，慢指针就位于倒数第 k 个节点的位置。

  4. 删除链表的倒数第 k 个节点：
    类似于找到倒数第 k 个节点的方法，一旦找到该节点，就可以进行删除操作。

  5. 判断回文链表：
    首先使用快慢指针找到链表的中点，然后反转链表的后半部分，最后比较前半部分和反转后的后半部分是否相同。

  6. 元素移动：
    快慢指针在处理诸如将所有特定值移动到数组一端的问题中非常有用，同时保持其他元素的相对顺序。 - 实现方法：慢指针指向下一个非特定值（如非零值）应该放置的位置，快指针遍历数组。当快指针发现一个非特定值时，如果快指针和慢指针不在同一位置，就将其值复制到慢指针的位置，并将原位置设为特定值（如零）。

  7. 数据分区：
    快慢指针可用于将数据根据某种条件分成两部分，类似于快速排序中的分区操作。- 实现方法：快指针遍历整个数组，慢指针跟踪分区的边界。当快指针指向的元素满足某个条件时（如小于给定值），将其与慢指针指向的元素交换，然后慢指针向前移动一步。这样，慢指针左边的所有元素都满足条件，右边的不满足。

3. 滑动窗口（Sliding Window）

  • 思路：利用两个指针（窗口的左边界和右边界）在序列上形成一个窗口，根据需求调整窗口的大小（或位置），从而解决子数组或子串的问题。
  • 适用场景：常用于求解具有特定条件的连续子数组或子串问题，如「最长无重复子串」、「最小覆盖子串」等。
  • 例子：在寻找无重复字符的最长子串时，右指针扩展窗口，左指针缩小窗口，保证窗口内无重复字符。链接：无重复字符的最长子串
  • 滑动窗口的核心是如何定义一个窗口，即窗口内是什么？
  • 解决"无重复字符的最长子串"问题的具体方法可以通过滑动窗口技术实现，这里我提供一个具体的 C++ 实现步骤和代码，以及一些记忆技巧来帮助你理解和记住关键概念。

具体解决方法（C++ 实现）

  1. 定义变量：使用两个指针 left 和 right 来表示滑动窗口的边界。使用一个哈希表 map<char, int> 来记录每个字符最后出现的位置。
  2. 初始化：left 和 right 都从 0 开始。定义 maxLen 来保存最长子串的长度。
  3. 扩展右边界：遍历字符串，移动 right 指针。对于每个新的字符，如果该字符已经在哈希表中，并且它的位置在 left 的右边，将 left 移动到该字符上次出现位置的下一个位置（为了排除重复字符）。
  4. 更新记录：更新哈希表中当前字符的位置。同时更新最长子串的长度 maxLen。
  5. 返回结果：遍历完成后，maxLen 即为所求的最长无重复字符子串的长度。
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charIndexMap;
    int maxLen = 0, left = 0;

    for (int right = 0; right < s.length(); right++) {
        if (charIndexMap.find(s[right]) != charIndexMap.end()) {
            left = max(left, charIndexMap[s[right]] + 1);
        }
        charIndexMap[s[right]] = right;
        maxLen = max(maxLen, right - left + 1);
    }

    return maxLen;
}

int main() {
    string s = "abcabcbb";
    cout << "Length of longest substring without repeating characters: " << lengthOfLongestSubstring(s) << endl;
    return 0;
}

记忆技巧

  • 滑动窗口：想象一个窗口滑过字符串，窗口内是独特的字符集。左边界和右边界分别用两个指针控制。
  • 哈希表记录：哈希表用来迅速判断字符是否重复，并记录最新的位置，帮助调整窗口的左边界。
  • 边界调整：每次遇到重复的字符，就移动左边界到重复字符上一次出现后的位置。这就像是"跳过"了之前的重复，直接从重复结束的地方开始新的计算。
  • 最大长度更新：在每个步骤中，都检查并更新当前窗口的大小是否是最大的。

通过这些步骤和记忆技巧，你可以更好地理解和记住如何解决这类问题。

4. 区间合并（Merging Intervals）

  • 思路：在处理排序好的区间时，双指针用于合并或操作区间，通常一个指针指向当前正在处理的区间，另一个指针逐一检查后续区间是否可以合并。
  • 适用场景：用于区间合并、区间覆盖等问题，如「合并区间」、「插入区间」等。
  • 例子：在合并区间问题中，通过检查两个区间是否重叠来决定合并或新增区间。

5. 双指针遍历（Two Pointers for Iteration）

  • 思路：同时使用两个指针遍历同一个或不同的序列，以解决查找、比较、或匹配问题。
  • 适用场景：常用于合并排序数组、链表的交集等问题。
  • 例子：在合并两个有序数组时，使用两个指针分别遍历两个数组，将较小的元素依次放入结果数组中。

6. 分离双指针（Separated Pointers）

  • 思路：两个指针分别遍历两个独立的序列，寻找满足特定条件的配对，或者查找目标值。
  • 适用场景：如「四数之和」、「两个数组的交集」等问题。
  • 例子：在「两个数组的交集」问题中，使用双指针同时遍历两个排序数组，找到相同的元素。

7. 双指针优化动态规划（Two Pointers to Optimize DP）

  • 思路：利用双指针技巧优化动态规划问题，减少冗余计算，提高效率。
  • 适用场景：如「最长有效括号」、「最大子数组和」等问题。
  • 例子：在某些情况下，通过双指针维护动态规划状态，可以减少内层循环的复杂度，从而优化问题。

8. 双指针划分子问题（Divide and Conquer with Two Pointers）

  • 思路：使用双指针划分问题的不同子部分，分别解决，然后合并结果。
  • 适用场景：如「归并排序」等问题。
  • 例子：归并排序中使用双指针合并两个排序数组。

总结

双指针技术的核心在于通过两个指针的协同工作，减少问题的规模或复杂度。它们在数组、链表、字符串等结构中有广泛应用。每种思路都有其特定的应用场景，通过巧妙地选择和移动指针，可以大大提高算法的效率。

# c++ # 开发语言
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR 技术科普：光波导是什么，为什么警务要用它

avatar 乐奇 Rokid 开放社区
cover

光感日常，电懂人心：消费电子与生活的光电融合

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区