C++程序实现的双指针技术

双指针技术是一种简单有效的技术，通常用于在排序数组中搜索对。

给定一个按升序排序的数组A，其中有N个整数，请找出是否存在任何一对元素(A[i], A[j])，使它们的和等于X。

让我们看一下 最初级的解决方案 。

// 在A [0..N-1]中查找是否存在一对的最初级解决方案。
#include <bits/stdc++.h>
using namespace std;
 
bool isPairSum (int A []，int N，int X)
{
    for (int i = 0; i < N; i ++)
    {
      for (int j = 0; j < N; j ++)
      {
         //由于i和j相等表示相同的元素
         if (i == j)
            继续执行;
           
         //存在对
         if (A [i] + A [j] == X)
            返回真;
 
         //由于数组已排序
         if (A [i] + A [j]> X)
            休息;
      }
    }
 
    //没有找到给定总和的任何对。
    返回假;
}
 
//驱动程序
int main()
{
    int arr [] = {3,5,9,2,8,10,11};
    int val = 17;
    int arrSize = *(&Amp;arr + 1) - arr;
    sort(arr，arr + arrSize); //对数组进行排序
    //函数调用
    cout << isPairSum (arr，arrSize，val);
 
    return 0;
}

输出

时间复杂度： O(n 2 )

辅助空间： O(1)

现在让我们看看双指针技术如何工作。我们取两个指针，一个表示数组的第一个元素，另一个表示数组的最后一个元素，然后将保持在这两个指针上的值相加。如果它们的总和小于X，则将左指针向右移动，如果它们的总和大于X，则向左移动右指针，以便更接近总和。我们不断移动指针，直到获得总和为X。

#include <iostream>
using namespace std;

// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
    // represents first pointer
    int i = 0;

    // represents second pointer
    int j = N - 1;

    while (i < j) {

        // If we find a pair
        if (A[i] + A[j] == X)
            return 1;

        // If sum of elements at current
        // pointers is less, we move towards
        // higher values by doing i++
        else if (A[i] + A[j] < X)
            i++;

        // If sum of elements at current
        // pointers is more, we move towards
        // lower values by doing j--
        else
            j--;
    }
    return 0;
}

// Driver code
int main()
{
    // array declaration
    int arr[] = { 3, 5, 9, 2, 8, 10, 11 };

    // value to search
    int val = 17;

    // size of the array
    int arrSize = *(&arr + 1) - arr;

    // Function call
    cout << (bool)isPairSum(arr, arrSize, val);

    return 0;
}

输出：

示例说明：

C++程序实现的双指针技术