ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด N หน้าที่ของเราคือ ค้นหาดัชนีของตัวชี้ด้านซ้ายหลังจากการย้ายที่เป็นไปได้ในอาร์เรย์ .
เรามีพอยน์เตอร์สองตัวสำหรับอาร์เรย์ ตัวชี้ซ้ายตัวหนึ่งและตัวชี้ขวาอีกตัว
ตัวชี้ด้านซ้ายเริ่มต้นที่ดัชนี 0 และค่าจะเพิ่มขึ้น
ตัวชี้ขวาเริ่มต้นที่ดัชนี (n-1) และค่าจะลดลง
ค่าของตัวชี้จะเพิ่มขึ้นหากผลรวมที่ผ่านน้อยกว่าค่าอื่น กล่าวคือ ถ้าผลรวมของตัวชี้ด้านซ้ายน้อยกว่าผลรวมของตัวชี้ด้านขวา ตัวชี้ด้านซ้ายจะเพิ่มขึ้น มิฉะนั้น ค่าของตัวชี้ทางขวาจะลดลง และมีการอัพเดทผลรวม
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2 คำอธิบาย −
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.
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการย้าย leftPointer และ rightPointer ตามผลรวม จากนั้นตรวจสอบว่า leftPointer มีค่ามากกว่า rightPointer หรือไม่
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
