C++双指针算法基础

1.1 算法复杂度概念简介

• 时间复杂度：衡量算法执行时间随输入规模增长的变化趋势
• 常见时间复杂度：
  • ：常数时间，不随输入规模变化
  • ：对数时间，随输入规模对数增长
  • ：线性时间，与输入规模成正比
  • ：平方时间，与输入规模的平方成正比
• 双指针的优势：将许多需要嵌套循环的问题从优化到
• 实际意义：当时，算法需要约10000次操作，而算法需要约1亿次操作

1.2 指针的含义

• 指针的概念：在双指针算法中，"指针"是指向数据结构中特定位置的索引或标记
• 与C++指针的区别：
  • 双指针算法中的指针通常是数组索引（整数），而非实际内存地址
  • 不涉及直接的内存操作，仅用于标记处理位置
• 指针的作用：
  • 标记当前处理的位置
  • 协调两个位置之间的操作
  • 控制算法流程和边界条件
• 指针的特点：根据问题要求按特定规则移动，通过协同工作解决问题

1.3 双指针概述

• 双指针(Two Pointers) : 是一种使用两个指针在线性结构（数组、字符串等）上协同工作以解决问题的算法技巧
• 核心思想：通过控制两个指针的移动，将时间复杂度从 降低到
• 基本前提：数据结构通常是数组、链表或字符串等线性结构
• 双指针的两种主要形式：
  • 同向双指针：两个指针从同一侧出发，通常用于滑动窗口、快慢指针等
  • 相向双指针：两个指针从两端向中间移动，通常用于查找、排序等，也成为碰撞双指针

2.1 双指针的特点

• 高效性：时间复杂度通常为，比暴力方法快得多
• 空间效率：通常只需要的额外空间，可以原地操作
• 适用范围：主要用于线性数据结构（数组、链表、字符串）
• 实现简单：思路清晰，代码简洁，易于理解和实现
• 灵活多变：可以根据问题特点调整指针的初始位置、移动规则和终止条件
• 前提条件：某些应用场景（如相向双指针）可能需要数据有序或满足特定性质

3.1 同向双指针基本模板

// 同向双指针基本模板
void twoPointersSameDirection(vector<int>& nums) {
    int n = nums.size();
    int left = 0;  // 左指针初始位置
    int right = 0; // 右指针初始位置（也可以是其他位置）
    
    while (right < n) {
        // 更新状态或进行计算
        // ...
        
        // 移动右指针
        right++;
        
        // 根据条件移动左指针
        while (left < right && /* 某些条件 */) {
            // 可能需要在移动前更新状态
            // ...
            left++;
        }
        
        // 处理当前窗口的结果
        // ...
    }
    
    // 返回最终结果
    // ...
}

3.2 相向双指针基本模板

// 相向双指针基本模板
void twoPointersOppositeDirection(vector<int>& nums) {
    int n = nums.size();
    int left = 0;          // 左指针初始位置
    int right = n - 1;     // 右指针初始位置
    
    while (left < right) {
        // 计算或比较当前指针指向的元素
        // ...
        
        // 根据条件移动指针
        if (/* 某些条件 */) {
            left++;
        } else {
            right--;
        }
        
        // 可能需要跳过重复元素
        while (left < right && nums[left] == nums[left - 1]) left++;
        while (left < right && nums[right] == nums[right + 1]) right--;
    }
    
    // 返回最终结果
    // ...
}

3.3 快慢指针模板

// 快慢指针模板（以链表为例）
ListNode* fastSlowPointers(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode* slow = head;        // 慢指针
    ListNode* fast = head->next;  // 快指针
    
    // 快指针每次移动两步，慢指针每次移动一步
    while (fast && fast->next) {
        slow = slow->next;        // 慢指针移动一步
        fast = fast->next->next;  // 快指针移动两步
        
        // 根据问题处理特定情况
        // 例如：检测环
        if (slow == fast) {
            // 找到环
            // ...
            break;
        }
    }
    
    // 返回结果（如链表中点、环的入口等）
    // ...
    return slow;  // 或其他结果
}

3.4 滑动窗口模板

// 滑动窗口模板
int slidingWindow(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = 0;
    int sum = 0;  // 或其他状态变量
    int result = 0;  // 或其他结果变量
    
    while (right < n) {
        // 扩展窗口
        sum += nums[right];  // 更新状态
        right++;
        
        // 根据条件收缩窗口
        while (left < right && /* 窗口需要收缩的条件 */) {
            sum -= nums[left];  // 更新状态
            left++;
        }
        
        // 更新结果
        // ...
    }
    
    return result;
}

3.5 双指针在有序数组中的应用模板

// 有序数组中的双指针模板（以两数之和为例）
vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        
        if (sum == target) {
            return {left, right};  // 找到目标
        } else if (sum < target) {
            left++;  // 和太小，增加左指针
        } else {
            right--;  // 和太大，减小右指针
        }
    }
    
    return {-1, -1};  // 未找到目标
}

3.6 双指针在链表中的应用模板

// 链表中的双指针模板（以删除倒数第N个节点为例）
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    
    ListNode* first = dummy;
    ListNode* second = dummy;
    
    // 先让第一个指针前进n+1步
    for (int i = 0; i <= n; i++) {
        first = first->next;
    }
    
    // 两个指针同时前进，直到第一个指针到达末尾
    while (first) {
        first = first->next;
        second = second->next;
    }
    
    // 此时second指向要删除节点的前一个节点
    ListNode* temp = second->next;
    second->next = second->next->next;
    delete temp;
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

3.7 双指针在字符串中的应用模板

// 字符串中的双指针模板（以判断回文串为例）
bool isPalindrome(string s) {
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        
        // 比较字符（忽略大小写）
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

4.1 实例分析：两数之和（有序数组）

问题描述：
给定一个已按照升序排列的整数数组numbers，请找出两个数，使得它们相加之和等于目标数target。函数应该返回这两个数的下标（从1开始计数），而且下标1必须小于下标2。

分析：

• 由于数组已经排序，可以使用相向双指针
• 初始化左指针指向数组开头，右指针指向数组末尾
• 计算两指针所指元素之和，与目标值比较
• 如果和等于目标值，返回两个指针的位置
• 如果和小于目标值，增加左指针（使和变大）
• 如果和大于目标值，减小右指针（使和变小）

4.2 实例分析：移除元素

问题描述：
给定一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，必须在原地修改输入数组并使用O(1)额外空间的条件下完成。

分析：

• 使用快慢指针的思想
• 慢指针slow指向当前需要填入新元素的位置
• 快指针fast用于遍历数组
• 当fast指向的元素不等于val时，将其复制到slow位置，并增加slow
• 最终slow的值就是新数组的长度

4.3 实例分析：盛最多水的容器

问题描述：
给定一个长度为n的整数数组height，有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

分析：

• 使用相向双指针，初始时指向数组的两端
• 容器的面积由两个因素决定：两条线的距离和两条线中较短的那条
• 面积计算公式：min(height[left], height[right]) * (right - left)
• 为了找到可能的最大面积，每次移动较短的那条线对应的指针
• 因为如果移动较长的线，容器的高度不会增加，而宽度会减小，面积一定会减小

4.4 实例分析：三数之和

问题描述：
给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a, b, c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。

分析：

• 首先对数组进行排序，这样可以使用双指针技巧
• 固定第一个数，然后使用双指针寻找剩下两个数
• 为了避免重复解，需要跳过重复的元素
• 当三数之和等于0时，记录结果并移动双指针
• 当三数之和小于0时，增加左指针
• 当三数之和大于0时，减小右指针

4.5 实例分析：链表中环的检测

问题描述：
给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。

分析：

• 使用快慢指针（Floyd's Tortoise and Hare算法）
• 慢指针每次移动一步，快指针每次移动两步
• 如果存在环，两个指针最终会在环中相遇
• 如果不存在环，快指针会先到达链表末尾

进阶：找到环的入口点

• 当快慢指针相遇时，将其中一个指针重置到链表头部
• 然后两个指针都每次移动一步
• 它们会在环的入口点相遇

4.6 实例分析：滑动窗口最大值

问题描述：
给定一个数组nums和滑动窗口的大小k，请找出所有滑动窗口里的最大值。

分析：

• 使用双端队列来维护一个单调递减的队列
• 队列中存储的是元素的索引，而不是元素本身
• 队首元素始终是当前窗口中的最大值
• 当新元素进入窗口时：
  • 移除队列中所有小于新元素的值（保持单调性）
  • 将新元素的索引加入队列尾部
• 当元素离开窗口时，如果它在队首，则将其移除

5.1 基础练习题

1. [POJ 2739] Sum of Consecutive Prime Numbers

   • 难度：★★☆☆☆
   • 描述：找出所有连续质数的和等于给定数的方案数
   • 知识点：同向双指针，滑动窗口

2. [HDU 1392] Surround the Trees

   • 难度：★★☆☆☆
   • 描述：求包围所有点的最小周长凸多边形
   • 知识点：相向双指针，凸包算法

3. [CSP-J 2019] 数列

   • 难度：★★☆☆☆
   • 描述：在有序数组中查找满足特定条件的元素
   • 知识点：相向双指针，二分查找

5.2 中级练习题

1. [USACO 2016 Feb Silver] Load Balancing

   • 难度：★★★☆☆
   • 描述：通过划分平面使四个区域中的点数尽可能平衡
   • 知识点：双指针扫描，二分思想

2. [NOIP 2015] 子串

   • 难度：★★★☆☆
   • 描述：求两个字符串的最长公共子串
   • 知识点：滑动窗口，字符串匹配

3. [CSES 1640] Sum of Two Values

   • 难度：★★★☆☆
   • 描述：在数组中找到和为给定值的两个元素
   • 知识点：相向双指针，哈希表

5.3 高级练习题

1. [CSP-S 2019] 树的重心

   • 难度：★★★★☆
   • 描述：求树的重心，使得删除该节点后的最大连通块最小
   • 知识点：树上双指针，深度优先搜索

2. [POJ 3061] Subsequence

   • 难度：★★★★☆
   • 描述：求和不小于给定值的最短连续子数组
   • 知识点：滑动窗口，前缀和

3. [HDU 3549] Flow Problem

   • 难度：★★★★☆
   • 描述：求网络最大流
   • 知识点：双指针在图论中的应用，最大流算法

5.4 综合应用题

1. [NOIP 2016] 换教室

   • 难度：★★★★★
   • 描述：安排课程使得换教室的次数最少
   • 知识点：双指针与动态规划结合

2. [USACO 2019 Jan Gold] Sleepy Cow Sorting

   • 难度：★★★★★
   • 描述：求将数组排序所需的最少操作次数
   • 知识点：双指针与贪心算法结合

3. [IOI 2015] Teams

   • 难度：★★★★★
   • 描述：将学生分成若干组，使得每组的能力值在给定范围内
   • 知识点：双指针与二分查找结合