在这个问题中,我们给出了一个大小为N的数组arr[]。我们的任务是在数组中可能的移动后找到左指针的索引。
我们有两个指针,一个是左指针,另一个是右指针。
左指针从索引0开始,值递增。
右指针从索引(n-1)开始,值递减。
如果左指针的和小于右指针的和,则指针的值增加,否则指针的值减少。并且和的值会更新。
让我们通过一个例子来理解这个问题,
'Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2
Explanation −
的中文翻译为:Explanation −
'leftPointer = 0 -> sum = 5, rightPointer = 5 -> sum = 4. Move rightPointer
leftPointer = 0 -> sum = 5, rightPointer = 4 -> sum = 13. Move leftPointer
leftPointer = 1 -> sum = 11, rightPointer = 4 -> sum = 13. Move leftPointer
leftPointer = 2 -> sum = 14, rightPointer = 4 -> sum = 13. Move rightPointer
leftPointer = 2 -> sum = 14, rightPointer = 3 -> sum = 20. Move rightPointer
Position of the left pointer is 2.
解决方案
通过根据和的大小移动左指针和右指针来解决问题。然后检查左指针是否比右指针大1。
示例
程序示例,说明我们解决方案的工作原理
'#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
if(n == 1)
return 0;
int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
while (rightPointer > leftPointer + 1) {
if (leftPointerSum < rightPointerSum) {
leftPointer++;
leftPointerSum += arr[leftPointer];
}
else if (leftPointerSum > rightPointerSum) {
rightPointer--;
rightPointerSum += arr[rightPointer];
}
else {
break;
}
}
return leftPointer;
}
int main() {
int arr[] = { 5, 6, 3, 7, 9, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
return 0;
}
输出
'The index of left pointer after moving is 2