มาดูขั้นตอนในการจบโปรแกรมกัน
- เริ่มต้นอาร์เรย์
- ทำให้เลขศูนย์ทั้งหมดในอาร์เรย์เป็น -1
- มีแผนที่เป็นแผนที่ว่างเพื่อจัดเก็บดัชนีก่อนหน้า
- เริ่มต้นผลรวมเป็น 0, ความยาวสูงสุดเป็น 0 และสิ้นสุดดัชนีเป็น -1
- เขียนลูปที่วนซ้ำจนถึง n.
- เพิ่มองค์ประกอบปัจจุบันเพื่อรวม
- ถ้าผลรวมเท่ากับ 0
- อัปเดตความยาวสูงสุดด้วย i + 1
- และลงท้ายด้วยดัชนี i.
- หากผลรวมมีอยู่ในแผนที่ผลรวมก่อนหน้าและ i - PreviousIndexes[sum] มากกว่าความยาวสูงสุด
- อัปเดตความยาวสูงสุดและดัชนีสิ้นสุด
- อย่างอื่นเพิ่มผลรวมในแมปดัชนีก่อนหน้า
- พิมพ์ดัชนีเริ่มต้น endingIndex - maxLength + 1 และสิ้นสุดดัชนี endingIndex
ตัวอย่าง
มาดูโค้ดกันเลย
#include <bits/stdc++.h>
using namespace std;
void findTheSubArray(int arr[], int n) {
unordered_map<int, int> previousIndexes;
int sum = 0, maxLength = 0, endingIndex = -1;
for (int i = 0; i < n; i++) {
arr[i] = arr[i] == 0 ? -1 : 1;
}
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 0) {
maxLength = i + 1;
endingIndex = i;
}
if (previousIndexes.find(sum) != previousIndexes.end()) {
if (maxLength < i - previousIndexes[sum]) {
maxLength = i - previousIndexes[sum];
endingIndex = i;
}
}else {
previousIndexes[sum] = i;
}
}
cout << endingIndex - maxLength + 1 << " " << endingIndex << endl;
}
int main() {
int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 };
findTheSubArray(arr, 9);
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
1 8
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
