双指针是一种通过两个变量在数组中按特定条件移动以优化遍历效率的算法思想，常用于减少时间复杂度。1. 对向双指针适用于有序数组，如两数之和问题，left从头、right从尾相向而行，根据和与目标关系决定移动方向，找到和为目标值的两个元素索引。2. 同向双指针常用于滑动窗口模型，如寻找满足和大于等于target的最短连续子数组，right扩展窗口，left在条件满足时收缩，实现O(n)时间复杂度。3. 使用时需注意数组有序性、指针越界及循环条件选择，该技巧适用于特定场景如回文判断、子数组优化等，能将O(n²)降至O(n)，但不适用于所有遍历情况。熟练掌握需理解移动逻辑并练习经典题目。
在C++中，双指针遍历数组是一种常见且高效的技巧，主要用于减少时间复杂度，避免使用嵌套循环。它通过设置两个指针在数组中移动，根据特定条件推进其中一个或两个指针，从而完成对数组的遍历或查找操作。
1. 双指针的基本概念
双指针并不是指C++中的指针变量类型，而是一种算法思想：使用两个变量（通常命名为left和right，或i和j）来遍历数组或容器。这两个“指针”实际上是数组下标，用来指向元素位置。
常见的双指针模式包括：
- 对向双指针：一个从头开始，一个从尾开始，相向移动，常用于有序数组的两数之和、回文判断等。
- 同向双指针（滑动窗口）：两个指针都从左侧开始，右指针先扩展，左指针根据条件收缩，适用于子数组问题。
2. 对向双指针示例：两数之和（有序数组）
假设有一个升序数组，找出两个数使它们的和等于目标值。
立即学习“C++免费学习笔记（深入）”；
#include#include using namespace std; vector
twoSum(vector & arr, int target) { int left = 0; int right = arr.size() - 1; while (left zuojiankuohaophpcn right) { int sum = arr[left] + arr[right]; if (sum == target) { return {left, right}; // 返回索引 } else if (sum zuojiankuohaophpcn target) { left++; // 和太小，左指针右移 } else { right--; // 和太大，右指针左移 } } return {-1, -1}; // 未找到}
int main() { vector
arr = {1, 3, 5, 8, 10}; auto result = twoSum(arr, 9); if (result[0] != -1) { cout
输出结果为：Indices: 1, 3，对应数值3和8。
3. 同向双指针示例：滑动窗口找最短子数组
给定一个正整数数组和目标值target，找出长度最小的连续子数组，使其和大于等于target。
#include#include #include using namespace std; int minSubArrayLen(int target, vector
& nums) { int left = 0, sum = 0; int minLen = INT_MAX; for (int right = 0; right zuojiankuohaophpcn nums.size(); right++) { sum += nums[right]; // 扩展右边界 while (sum >= target) { minLen = min(minLen, right - left + 1); sum -= nums[left]; // 收缩左边界 left++; } } return minLen == INT_MAX ? 0 : minLen;}
这个方法利用右指针扩展窗口，左指针在满足条件时收缩，时间复杂度为O(n)。
4. 使用建议与注意事项
双指针技巧适用场景有限，需注意以下几点：
- 对向双指针通常要求数组有序，否则无法判断移动方向。
- 同向双指针多用于连续子数组问题，尤其是涉及“最小长度”、“最大和”等优化目标。
- 移动指针时要防止越界，循环条件要写清楚，比如left 或left 根据需求选择。
- 双指针不能替代所有遍历方式，但在合适场景下能将O(n²)优化到O(n)。
基本上就这些。掌握双指针的关键是理解其移动逻辑和适用条件，多练习经典题目如“两数之和 II”、“三数之和”、“接雨水”等，就能熟练运用。
