c++中如何使用双指针查找元素_c++双指针查找数组元素技巧-C++-PHP中文网

c++中如何使用双指针查找元素_c++双指针查找数组元素技巧

尼克

发布： 2025-10-05 16:11:01

原创

731人浏览过

双指针通过两个索引变量在数组中协同移动，常用于有序数组的元素查找。其主要形式包括对撞指针（从两端向中间移动）、快慢指针（同向移动）和滑动窗口（一固定一滑动）。在查找两数之和时，利用对撞指针可在O(n)时间内找到目标值，避免暴力枚举的O(n²)复杂度。对于三数之和问题，先排序，再固定一个数，剩余部分使用双指针查找两数之和，将总时间复杂度优化至O(n²)，并需跳过重复元素以去重。该技巧适用于有序数组中的和查找、去重、合并数组、滑动窗口及链表环检测等问题，关键在于利用顺序性减少无效比较，但要求数组有序或配合其他结构如哈希表使用。

c++中如何使用双指针查找元素_c++双指针查找数组元素技巧

在C++中，双指针是一种高效处理数组或链表问题的技巧，尤其适用于有序数组中的元素查找。它通过两个指针从不同位置同时遍历，减少时间复杂度，避免暴力枚举。

双指针的基本思想

双指针不是真的指针变量，而是两个用于遍历数组的索引变量。它们可以：

从两端向中间移动（对撞指针）
一快一慢同向移动（快慢指针）
一个固定，另一个滑动（滑动窗口）

对于查找元素类问题，最常用的是对撞指针，特别是在有序数组中查找两数之和等于目标值的情况。

在有序数组中查找两数之和

假设有一个升序排列的数组，要找出两个数，使其和等于给定目标值。使用双指针可以从数组两端开始逼近：

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

#include <iostream>
#include <vector>
using namespace std;
<p>pair<int, int> findTwoSum(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;</p><pre class='brush:php;toolbar:false;'>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}; // 未找到

登录后复制

}

这个方法的时间复杂度是 O(n)，比暴力 O(n²) 快很多，且不需要额外哈希表空间。

Boomy

AI音乐生成工具，创建生成音乐,与世界分享.

272

查看详情

查找三数之和（进阶技巧）

三数之和问题也可以用双指针优化。基本思路是：

先排序数组
固定第一个数，然后对剩余部分使用双指针查找两数之和

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
<pre class='brush:php;toolbar:false;'>for (int i = 0; i < nums.size(); i++) {
    // 跳过重复元素
    if (i > 0 && nums[i] == nums[i-1]) continue;

    int left = i + 1, right = nums.size() - 1;
    int target = -nums[i];

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            result.push_back({nums[i], nums[left], nums[right]});
            // 跳过相同值
            while (left < right && nums[left] == nums[left+1]) left++;
            while (left < right && nums[right] == nums[right-1]) right--;
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
}
return result;

登录后复制

}

这种技巧将三重循环优化为 O(n²)，核心在于排序后利用有序性进行双指针搜索。