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

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;
}  

输出

1

时间复杂度: 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;
}

输出:

1

示例说明:

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

时间复杂度: O(n)

辅助空间: 因为只使用恒定的空间,所以为O(1)

工作原理是什么?

该算法基本上使用输入数组已排序的事实。我们从最小值和最大值的和开始,并有条件地移动两个指针。当A [i]和A [j]的总和小于X时,我们向左移动指针i。我们不会错过任何一对,因为总和已小于X。同样的逻辑适用于指针j的右侧。

基于双指针技术的更多问题。

  • 从两个已排序数组中找到最接近的一对
  • 在数组中找到与 x 最接近的一对
  • 找到所有三元组的和为零
  • 找到一个三元组,其总和等于给定值
  • 找到一个三元组,其两个元素的和等于第三个元素
  • 找到四个元素,使其总和等于给定值

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例