# 给定一个经过排序和旋转的数组，查找是否存在一对具有给定总和的数组 > 原文： [https://www.geeksforgeeks.org/given-a-sorted-and-rotated-array-find-if-there-is-a-pair-with-a-given-sum/](https://www.geeksforgeeks.org/given-a-sorted-and-rotated-array-find-if-there-is-a-pair-with-a-given-sum/) 给定一个已排序的数组，然后围绕未知点旋转。 查找数组是否具有给定总和为“`x`”的对。 可以假定数组中的所有元素都是不同的。 **示例**： ``` Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16 Output: true There is a pair (6, 10) with sum 16 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35 Output: true There is a pair (26, 9) with sum 35 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 45 Output: false There is no pair with sum 45. ``` 我们已经讨论了用于排序数组的[`O(n)`解（请参见方法 1 的步骤 2、3 和 4）](https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/)。 我们也可以将此解决方案扩展到旋转数组。 这个想法是首先找到数组中最大的元素，它也是枢轴点，紧随其后的元素是最小的元素。 一旦我们有了最大和最小元素的索引，就可以在中间算法（如方法 1 中的[此处](https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/)讨论的）中使用类似的 Meet 来查找是否存在一对。 唯一的新变化是使用模块化算法以循环方式递增和递减索引。 以下是上述想法的实现。 ## C++ ```cpp // C++ program to find a pair with a given sum in a sorted and // rotated array #include<iostream> using namespace std; // This function returns true if arr[0..n-1] has a pair // with sum equals to x. bool pairInSortedRotated(int arr[], int n, int x) {     // Find the pivot element     int i;     for (i=0; i<n-1; i++)         if (arr[i] > arr[i+1])             break;     int l = (i+1)%n;  // l is now index of smallest element     int r = i;        // r is now index of largest element     // Keep moving either l or r till they meet     while (l != r)     {          // If we find a pair with sum x, we return true          if (arr[l] + arr[r] == x)               return true;          // If current pair sum is less, move to the higher sum          if (arr[l] + arr[r] < x)               l = (l + 1)%n;          else  // Move to the lower sum side               r = (n + r - 1)%n;     }     return false; } /* Driver program to test above function */ int main() {     int arr[] = {11, 15, 6, 8, 9, 10};     int sum = 16;     int n = sizeof(arr)/sizeof(arr[0]);     if (pairInSortedRotated(arr, n, sum))         cout << "Array has two elements with sum 16";     else         cout << "Array doesn't have two elements with sum 16 ";     return 0; } ```