C++双指针算法教程

双指针算法是一种高效的算法技巧，广泛应用于数组、字符串和链表等线性数据结构的问题中。本教程将从基础概念开始，逐步引导你掌握双指针算法的核心思想和应用场景。

1. 什么是双指针算法？

双指针算法是指使用两个指针（变量）同时遍历数据结构，通过合理移动指针的位置来解决问题。与普通的单指针遍历相比，双指针可以大幅降低时间复杂度，提高算法效率。

双指针的核心思想：
通过两个指针的协作，将原本需要嵌套循环的问题转化为单次遍历，从而将时间复杂度从 O(n²) 优化到 O(n)。

2. 双指针的常见类型

双指针算法主要分为以下几种类型：

(1) 对撞指针（Two Pointers Opposite Direction）

• 特点： 两个指针分别从数组的两端向中间移动。
• 适用场景： 有序数组、查找配对、回文判断等。

(2) 快慢指针（Two Pointers Fast and Slow）

• 特点： 两个指针以不同的速度移动，通常快指针每次移动两步，慢指针每次移动一步。
• 适用场景： 链表环检测、中位数查找、删除重复元素等。

(3) 滑动窗口（Sliding Window）

• 特点： 两个指针形成一个窗口，通过移动窗口的左右边界来解决区间问题。
• 适用场景： 子数组求和、字符串匹配、最长子串等。

3. 对撞指针示例：两数之和

问题描述：
给定一个有序数组 nums 和一个目标值 target，找到数组中两个数的和等于 target，返回它们的下标。

示例代码：

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0;           // 左指针，指向数组开头
    int right = nums.size() - 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};  // 无解
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    
    vector<int> result = twoSum(nums, target);
    cout << "两数的下标分别为: " << result[0] << " 和 " << result[1] << endl;
    
    return 0;
}

输出结果：

两数的下标分别为: 0 和 1

算法思路：

• 初始化左指针 left 指向数组开头，右指针 right 指向数组末尾。
• 计算两指针所指元素的和 sum：
  • 如果 sum == target，则找到解，返回下标。
  • 如果 sum < target，说明需要更大的和，左指针右移。
  • 如果 sum > target，说明需要更小的和，右指针左移。
• 重复上述过程直到找到解或指针相遇。

4. 快慢指针示例：删除有序数组中的重复项

问题描述：
给定一个有序数组 nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

示例代码：

#include <iostream>
#include <vector>
using namespace std;

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]) {
            slow++;
            nums[slow] = nums[fast];  // 将不重复元素移动到慢指针位置
        }
    }
    
    return slow + 1;  // 新数组长度为慢指针位置加1
}

int main() {
    vector<int> nums = {1, 1, 2, 2, 3, 4, 4, 4, 5};
    
    int newLength = removeDuplicates(nums);
    
    cout << "删除重复项后的数组长度为: " << newLength << endl;
    cout << "删除重复项后的数组内容为: ";
    for (int i = 0; i < newLength; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果：

删除重复项后的数组长度为: 5
删除重复项后的数组内容为: 1 2 3 4 5 

算法思路：

• 初始化慢指针 slow 指向数组第一个元素。
• 使用快指针 fast 遍历数组：
  • 如果 nums[fast] 不等于 nums[slow]，说明遇到了新元素，将 slow 指针后移一位，并将 nums[fast] 的值赋给 nums[slow]。
• 遍历结束后，slow + 1 即为新数组的长度。

5. 滑动窗口示例：最大连续子数组和

问题描述：
给定一个整数数组 nums，找到一个具有最大和的连续子数组，返回其最大和。

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int currentSum = nums[0];  // 当前窗口的和
    int maxSum = nums[0];      // 最大和
    
    for (int i = 1; i < nums.size(); i++) {
        // 如果当前窗口的和为负数，丢弃当前窗口，从新元素开始
        currentSum = max(nums[i], currentSum + nums[i]);
        // 更新最大和
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    int maxSum = maxSubArray(nums);
    
    cout << "最大连续子数组和为: " << maxSum << endl;
    
    return 0;
}

输出结果：

最大连续子数组和为: 6

算法思路：

• 初始化当前窗口的和 currentSum 和最大和 maxSum 为数组的第一个元素。
• 从第二个元素开始遍历数组：
  • 对于每个元素，判断是将其加入当前窗口（currentSum + nums[i]）还是重新开始一个新窗口（nums[i]），取较大值更新 currentSum。
  • 每次更新 currentSum 后，比较其与 maxSum 的大小，更新 maxSum。
• 遍历结束后，maxSum 即为所求的最大连续子数组和。

6. 双指针算法的应用场景

双指针算法适用于以下场景：

• 有序数组/链表：对撞指针常用于有序数组的查找问题。
• 数组去重/删除元素：快慢指针可高效处理此类问题。
• 子数组/子串问题：滑动窗口是解决这类问题的利器。
• 环检测：快慢指针可检测链表中是否存在环。

7. 练习题

1. 反转字符串：编写一个函数，将输入的字符串反转。
2. 判断回文串：给定一个字符串，判断它是否是回文串（忽略大小写和非字母数字字符）。
3. 盛最多水的容器：给定 n 个非负整数，每个数代表坐标中的一个点 (i, ai)，找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

总结

双指针算法是一种高效且实用的算法技巧，通过合理运用对撞指针、快慢指针和滑动窗口，可以解决许多复杂的线性数据结构问题。掌握双指针算法的关键在于理解问题的特性，并选择合适的指针策略。通过不断练习，你将能够熟练运用双指针算法解决各种问题。

C++双指针算法入门教程

双指针算法是一种高效的算法技巧，广泛应用于数组、链表等线性数据结构的问题中。它通过使用两个指针在数据结构中协同移动，从而在不使用额外空间或减少时间复杂度的情况下解决问题。

1. 双指针算法基本概念

双指针算法通常包含以下两种形式：

• 对撞指针：两个指针分别从数组的两端开始向中间移动
• 快慢指针：两个指针以不同的速度在数组或链表中移动

2. 对撞指针示例：两数之和

问题描述：给定一个已排序的数组和一个目标值，找到数组中两个数的和等于目标值，并返回它们的下标。

解决思路：使用对撞指针，一个指针指向数组的开始，另一个指针指向数组的末尾。计算两个指针所指元素的和，如果和等于目标值，则返回下标；如果和小于目标值，则将左指针右移；如果和大于目标值，则将右指针左移。

下面是解决该问题的C++代码：

#include <iostream>
#include <vector>
using namespace std; // 使用标准命名空间，避免重复写std::

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0;
    int right = numbers.size() - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            return {left + 1, right + 1}; // 题目要求下标从1开始
        } else if (sum < target) {
            left++; // 和太小，左指针右移
        } else {
            right--; // 和太大，右指针左移
        }
    }
    
    return {}; // 没有找到符合条件的元素
}

int main() {
    vector<int> numbers = {2, 7, 11, 15};
    int target = 9;
    
    vector<int> result = twoSum(numbers, target);
    
    if (result.size() == 2) {
        cout << "下标分别为: " << result[0] << " 和 " << result[1] << endl;
    } else {
        cout << "没有找到符合条件的元素" << endl;
    }
    
    return 0;
}

代码解释：

• 函数twoSum接收一个已排序的整数数组和一个目标值作为参数
• 使用两个指针left和right分别指向数组的开始和末尾
• 在每次循环中，计算两个指针所指元素的和，并与目标值比较
• 根据比较结果移动指针，直到找到符合条件的元素或指针相遇

3. 快慢指针示例：删除有序数组中的重复项

问题描述：给定一个已排序的数组，原地删除重复出现的元素，使得每个元素只出现一次，返回删除后数组的新长度。

解决思路：使用快慢指针，慢指针指向当前不重复的元素位置，快指针遍历数组。当快指针找到一个与慢指针不同的元素时，将该元素移动到慢指针的下一个位置，并更新慢指针。

下面是解决该问题的C++代码：

#include <iostream>
#include <vector>
using namespace std; // 使用标准命名空间，避免重复写std::

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]) {
            slow++;
            nums[slow] = nums[fast]; // 将不同的元素移动到慢指针的下一个位置
        }
    }
    
    return slow + 1; // 返回新数组的长度
}

int main() {
    vector<int> nums = {1, 1, 2, 2, 2, 3, 4, 4, 5};
    
    int newLength = removeDuplicates(nums);
    
    cout << "新数组长度为: " << newLength << endl;
    cout << "删除重复项后的数组为: ";
    for (int i = 0; i < newLength; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    
    return 0;
}

代码解释：

• 函数removeDuplicates接收一个已排序的整数数组作为参数
• 使用两个指针slow和fast，slow指向当前不重复的元素，fast用于遍历数组
• 当fast找到一个与slow不同的元素时，将该元素移动到slow的下一个位置，并更新slow
• 最终返回slow + 1作为新数组的长度

4. 双指针算法的应用场景

双指针算法适用于以下场景：

• 数组或链表已排序
• 需要在不使用额外空间的情况下解决问题
• 需要在O(n)时间复杂度内解决问题

5. 练习题目推荐

1. 反转字符串：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

2. 合并两个有序数组：给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

3. 验证回文串：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

通过练习这些题目，你将更好地掌握双指针算法的应用。双指针算法是解决数组和链表问题的重要技巧，掌握它将对你的算法能力有很大提升。