C++程序给定排序和旋转的数组，查找是否存在给定和的一对

给定一个排序后，然后围绕一个未知点旋转的数组。查找数组是否具有给定和“x”的一对。可以假定数组中的所有元素都是不同的。

示例:

输入：arr[] = {11, 15, 6, 8, 9, 10}，x = 16
输出：true
有一对（6,10）和为16

输入：arr[] = {11, 15, 26, 38, 9, 10}，x = 35
输出：true
有一对（26,9）和为35

输入：arr[] = {11, 15, 26, 38, 9, 10}，x = 45
输出：false
没有和为45的一对。

我们已经讨论过一种针对排序数组的O（n）解决方法（请参见方法1的步骤2、3和4）。我们也可以将此解决方案扩展到旋转数组上。首先找到数组中最大的元素，这是枢轴点，最大元素后面的元素是最小元素。一旦我们有了最大和最小元素的索引，我们使用类似于中间相遇算法（如方法1中所述）来查找是否存在一对。这里唯一的新事物是使用模运算以旋转方式递增和递减索引。

下面是上述想法的实现。

输出 :

数组有两个元素和为16

上述解的时间复杂度为O(n)。使用二进制搜索方法在O（logn）内优化可以找到枢轴。

如何计算所有和为x的对数？

以下是逐步算法：

找到排序和旋转数组的枢轴元素。枢轴元素是数组中最大的元素。最小元素将与它相邻。
使用两个指针（称为left和right），其中左指针指向最小元素，右指针指向最大元素。
查找指针指向的两个元素的和。
如果和等于x，则增加计数。如果和小于x，则将左指针按旋转方式递增到下一个位置以增加和。如果和大于x，则将右指针按旋转方式递减到下一个位置以减少和。
重复步骤3和4，直到左指针不等于右指针或左指针不等于right pointer-1为止。
打印最终计数。

下面是上述算法的实现。

// C++程序查找给定和的已排序旋转数组中的对数。
#include<bits/stdc++.h>
using namespace std;
 
//此函数返回和等于x的对数。
int pairsInSortedRotated(int arr[], int n, int x)
{
    //查找枢轴元素。 枢轴元素
    //是数组的最大元素。
    int i;
    for (i = 0; i < n-1; i++)
        if (arr[i] > arr[i+1])
            break;
     
    // l是最小元素的索引。
    int l = (i + 1) % n;
     
    // r是最大元素的索引。
    int r = i;
     
    //变量用于存储数字的数量
    //对数。
    int cnt = 0;
 
    //查找由arr [l]和arr [r]形成的对的总和
    //并相应地更新l，r和cnt。
    while (l != r)
    {
        //如果我们找到和为x的一对，则
        //增加计数器，将l和r移动到
        //下一个元素。
        if (arr[l] + arr[r] == x){
            cnt++;
             
            //必须检查此条件，
            //否则l和r将相交，循环
            //永远不会终止。
            if(l == (r - 1 + n) % n){
                return cnt;
            }
             
            l = (l + 1) % n;
            r = (r - 1 + n) % n;
        }
 
        //如果当前对的总和较小，则移动到
        //更高的总和方向。
        else if (arr[l] + arr[r] < x)
            l = (l + 1) % n;
         
        //如果当前对的总和较大，请移动
        //到较低的总和方向。
        else
            r = (n + r - 1)%n;
    }
     
    return cnt;
}
 
/* 主程序来测试上述函数 */
int main()
{
    int arr[] = {11, 15, 6, 7, 9, 10};
    int sum = 16;
    int n = sizeof(arr)/sizeof(arr[0]);
 
    cout << pairsInSortedRotated(arr, n, sum);
     
    return 0;
}

输出：

时间复杂度： O(n)

辅助空间： O(1)

这种方法是由Nikhil Jindal推荐的。

方法：双指针方法

使用修改后的二分搜索算法查找旋转排序数组的旋转元素。
初始化两个指针，一个指向数组的最小元素，另一个指向数组的最大元素。
当左指针小于右指针时，重复步骤4到6。
计算由左右指针指向的元素的和。
如果总和等于给定的总和，则返回true。
如果总和大于给定的总和，则将右指针减少。如果总和少于给定的总和，则将左指针增加。
如果没有找到给定总和的一对，则返回false。

#include <iostream>
using namespace std;
 
bool pairInSortedRotated(int arr[], int n, int x)
{
    // 使用二分查找找到轴心元素
    int i;
    for (i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
            break;
 
    // 初始化左右指针
    int left = (i + 1) % n;
    int right = i;
 
    // 查找给定和的对
    while (left != right)
    {
        // 如果找到了给定和的对，返回true
        if (arr[left] + arr[right] == x)
            return true;
 
        // 如果和大于给定和，将右指针减1
        else if (arr[left] + arr[right] > x)
            right = (n + right - 1) % n;
 
        // 如果和小于给定和，将左指针加1
        else
            left = (left + 1) % n;
    }
 
    // 如果找不到给定和的对，返回false
    return false;
}
 
int main()
{
    int arr1[] = {11, 15, 6, 8, 9, 10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int x1 = 16;
 
    if (pairInSortedRotated(arr1, n1, x1))
        cout << "True";
    else
        cout << "False";
 
    cout << endl;
 
    int arr2[] = {11, 15, 26, 38, 9, 10};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int x2 = 35;
 
    if (pairInSortedRotated(arr2, n2, x2))
        cout << "True";
    else
        cout << "False";
 
    cout << endl;
 
    int arr3[] = {11, 15, 26, 38, 9, 10};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int x3 = 45;
 
    if (pairInSortedRotated(arr3, n3, x3))
        cout << "True";
    else
        cout << "False";
 
    return 0;
}

输出结果