# 給定一個經過排序和旋轉的數組，查找是否存在一對具有給定總和的數組 > 原文： [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; } ```