c++中如何使用双指针遍历数组_c++双指针遍历数组方法-C++-PHP中文网

c++中如何使用双指针遍历数组_c++双指针遍历数组方法

穿越時空

发布： 2025-09-28 15:57:02

原创

433人浏览过

双指针是一种通过两个变量在数组中按特定条件移动以优化遍历效率的算法思想，常用于减少时间复杂度。1. 对向双指针适用于有序数组，如两数之和问题，left从头、right从尾相向而行，根据和与目标关系决定移动方向，找到和为目标值的两个元素索引。2. 同向双指针常用于滑动窗口模型，如寻找满足和大于等于target的最短连续子数组，right扩展窗口，left在条件满足时收缩，实现O(n)时间复杂度。3. 使用时需注意数组有序性、指针越界及循环条件选择，该技巧适用于特定场景如回文判断、子数组优化等，能将O(n²)降至O(n)，但不适用于所有遍历情况。熟练掌握需理解移动逻辑并练习经典题目。

c++中如何使用双指针遍历数组_c++双指针遍历数组方法

在C++中，双指针遍历数组是一种常见且高效的技巧，主要用于减少时间复杂度，避免使用嵌套循环。它通过设置两个指针在数组中移动，根据特定条件推进其中一个或两个指针，从而完成对数组的遍历或查找操作。

1. 双指针的基本概念

双指针并不是指C++中的指针变量类型，而是一种算法思想：使用两个变量（通常命名为left和right，或i和j）来遍历数组或容器。这两个“指针”实际上是数组下标，用来指向元素位置。

常见的双指针模式包括：

对向双指针：一个从头开始，一个从尾开始，相向移动，常用于有序数组的两数之和、回文判断等。
同向双指针（滑动窗口）：两个指针都从左侧开始，右指针先扩展，左指针根据条件收缩，适用于子数组问题。

2. 对向双指针示例：两数之和（有序数组）

假设有一个升序数组，找出两个数使它们的和等于目标值。

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
using namespace std;
<p>vector<int> twoSum(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;</p><pre class='brush:php;toolbar:false;'>while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        return {left, right}; // 返回索引
    } else if (sum < target) {
        left++; // 和太小，左指针右移
    } else {
        right--; // 和太大，右指针左移
    }
}
return {-1, -1}; // 未找到

登录后复制

}

int main() { vector<int> arr = {1, 3, 5, 8, 10}; auto result = twoSum(arr, 9); if (result[0] != -1) { cout << "Indices: " << result[0] << ", " << result[1] << endl; } return 0; }

输出结果为：Indices: 1, 3，对应数值3和8。

UP简历

基于AI技术的免费在线简历制作工具

128

查看详情

3. 同向双指针示例：滑动窗口找最短子数组

给定一个正整数数组和目标值target，找出长度最小的连续子数组，使其和大于等于target。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
<p>int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, sum = 0;
int minLen = INT_MAX;</p><pre class='brush:php;toolbar:false;'>for (int right = 0; right < 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)。